The cl-earley-parser Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The cl-earley-parser Reference Manual

This is the cl-earley-parser Reference Manual, version 1.0, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 03:43:22 2022 GMT+0.

Table of Contents


1 Introduction

cl-earley-parser

A natural language parser using Jay Earleys well-known algorithm.

Example usage:

CL-USER> (require :asdf)
:ASDF
("ASDF")
CL-USER> (asdf:oos 'asdf:load-op 'cl-earley-parser)
NIL
CL-USER> (use-package :earley-parser)
T
CL-USER> (earley-parse "Book that flight"\
	 	       (load-bnf-grammar "./examples/grammar.txt")\
		       (load-lexicon "./examples/lexicon.txt"))

#CHART-LISTING:
  0. #CHART:
    #{G ->  . S  [0,0]}
    #{S ->  . NP VP  [0,0]}
    #{S ->  . VP  [0,0]}
    #{S ->  . Aux NP VP  [0,0]}
    #{NP ->  . det nominal  [0,0]}
    #{NP ->  . proper-noun  [0,0]}
    #{VP ->  . verb  [0,0]}
    #{VP ->  . verb NP  [0,0]}
  1. #CHART:
    #{verb -> Book  .  [0,1]}
    #{VP -> verb  .  [0,1]}
    #{VP -> verb  . NP  [0,1]}
    #{S -> VP  .  [0,1]}
    #{NP ->  . det nominal  [1,1]}
    #{NP ->  . proper-noun  [1,1]}
    #{G -> S  .  [0,1]}
  2. #CHART:
    #{det -> that  .  [1,2]}
    #{NP -> det  . nominal  [1,2]}
    #{nominal ->  . noun  [2,2]}
    #{nominal ->  . noun nominal  [2,2]}
  3. #CHART:
    #{noun -> flight  .  [2,3]}
    #{nominal -> noun  .  [2,3]}
    #{nominal -> noun  . nominal  [2,3]}
    #{NP -> det nominal  .  [1,3]}
    #{nominal ->  . noun  [3,3]}
    #{nominal ->  . noun nominal  [3,3]}
    #{VP -> verb NP  .  [0,3]}
    #{S -> VP  .  [0,3]}
    #{G -> S  .  [0,3]}

CL-USER> (chart-listing->trees *)
(("S" ("VP" ("verb" "Book") ("NP" ("det" "that") ("nominal" ("noun" "flight"))))))
CL-USER>

2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 cl-earley-parser

Natural language parser using Jay Earleys well-known algorithm

Author

<Øyvin Halfdan Thuv - @oyvinht>

License

MIT

Version

1.0

Dependency

split-sequence (system).

Source

cl-earley-parser.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


3.1.1 cl-earley-parser/cl-earley-parser.asd

Source

cl-earley-parser.asd.

Parent Component

cl-earley-parser (system).

ASDF Systems

cl-earley-parser.


3.1.2 cl-earley-parser/defpackage.lisp

Source

cl-earley-parser.asd.

Parent Component

cl-earley-parser (system).

Packages

earley-parser.

Internals

3.1.3 cl-earley-parser/object-representations.lisp

Dependency

defpackage.lisp (file).

Source

cl-earley-parser.asd.

Parent Component

cl-earley-parser (system).

Public Interface
Internals

3.1.4 cl-earley-parser/grammar-reader.lisp

Dependencies
Source

cl-earley-parser.asd.

Parent Component

cl-earley-parser (system).

Public Interface
Internals

3.1.5 cl-earley-parser/earley-parser.lisp

Dependencies
Source

cl-earley-parser.asd.

Parent Component

cl-earley-parser (system).

Public Interface

earley-parse (function).

Internals

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 earley-parser

Source

defpackage.lisp.

Use List
  • common-lisp.
  • common-lisp-user.
Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


5.1.1 Ordinary functions

Function: earley-parse (sentence grammar lexicon)

Convert a string of words into a chart conforming to the grammar.

Package

earley-parser.

Source

earley-parser.lisp.

Function: load-bnf-grammar (pathname)

Reads a grammar on Backus-Naur form into the representation of the context free grammar(CFG).

Package

earley-parser.

Source

grammar-reader.lisp.

Function: load-lexicon (pathname)

Read all words from a dictionary file into a lexicon and a part of speech.

Package

earley-parser.

Source

grammar-reader.lisp.


5.1.2 Generic functions

Generic Function: chart-listing->trees (chart-listing)
Package

earley-parser.

Methods
Method: chart-listing->trees ((chart-listing chart-listing))

Return a list of trees created by following each successful parse in the last chart of ’chart-listings’

Source

object-representations.lisp.


5.1.3 Standalone methods

Method: print-object ((chart-listing chart-listing) (s stream))
Source

object-representations.lisp.

Method: print-object ((state state) (s stream))
Source

object-representations.lisp.

Method: print-object ((chart chart) (s stream))
Source

object-representations.lisp.


5.2 Internals


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.1 Special variables

Special Variable: *debug*
Package

earley-parser.

Source

defpackage.lisp.

Special Variable: *string-comparer*

equalp = case insensitive

Package

earley-parser.

Source

defpackage.lisp.

Special Variable: *whitespace*
Package

earley-parser.

Source

defpackage.lisp.


5.2.2 Ordinary functions

Reader: chart-listing-charts (instance)
Writer: (setf chart-listing-charts) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

charts.

Function: chart-listing-p (object)
Package

earley-parser.

Source

object-representations.lisp.

Function: chart-p (object)
Package

earley-parser.

Source

object-representations.lisp.

Reader: chart-states (instance)
Writer: (setf chart-states) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

states.

Function: completer (state chart-listing)

Find and return a list of the previous states that expect this states category at this dot-index with the dot moved one step forward. As a side-effect, enqeue the states in the current chart.

Package

earley-parser.

Source

earley-parser.lisp.

Function: copy-chart (instance)
Package

earley-parser.

Source

object-representations.lisp.

Function: copy-chart-listing (instance)
Package

earley-parser.

Source

object-representations.lisp.

Function: copy-grammar (instance)
Package

earley-parser.

Source

object-representations.lisp.

Function: copy-lexicon (instance)
Package

earley-parser.

Source

object-representations.lisp.

Function: copy-state (instance)
Package

earley-parser.

Source

object-representations.lisp.

Function: copy-terminal (instance)
Package

earley-parser.

Source

object-representations.lisp.

Function: grammar-p (object)
Package

earley-parser.

Source

object-representations.lisp.

Reader: grammar-rules (instance)
Writer: (setf grammar-rules) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

rules.

Reader: lexicon-dictionary (instance)
Writer: (setf lexicon-dictionary) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

dictionary.

Function: lexicon-p (object)
Package

earley-parser.

Source

object-representations.lisp.

Reader: lexicon-part-of-speech (instance)
Writer: (setf lexicon-part-of-speech) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

part-of-speech.

Function: make-chart (&key states)
Package

earley-parser.

Source

object-representations.lisp.

Function: make-chart-listing (&key charts)
Package

earley-parser.

Source

object-representations.lisp.

Function: make-grammar (&key rules)
Package

earley-parser.

Source

object-representations.lisp.

Function: make-lexicon (&key dictionary part-of-speech)
Package

earley-parser.

Source

object-representations.lisp.

Function: make-state (&key condition subtree dot constituent-index dot-index source-states)
Package

earley-parser.

Source

object-representations.lisp.

Function: make-terminal (&key class gender word)
Package

earley-parser.

Source

object-representations.lisp.

Function: read-lexicon-line (file)

Read a line from the given file, and return the corresponding terminal.

Package

earley-parser.

Source

grammar-reader.lisp.

Function: read-next-bnf-lexeme (file &optional keep-newline)

Reads and returns the next Backus-Naur lexeme from file.

Package

earley-parser.

Source

grammar-reader.lisp.

Function: read-next-bnf-production (file &optional keep-newline)

Reads and returns the next Backus-Naur production from file.

Package

earley-parser.

Source

grammar-reader.lisp.

Reader: state-condition (instance)
Writer: (setf state-condition) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

condition.

Reader: state-constituent-index (instance)
Writer: (setf state-constituent-index) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

constituent-index.

Reader: state-dot (instance)
Writer: (setf state-dot) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

dot.

Reader: state-dot-index (instance)
Writer: (setf state-dot-index) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

dot-index.

Function: state-p (object)
Package

earley-parser.

Source

object-representations.lisp.

Reader: state-source-states (instance)
Writer: (setf state-source-states) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

source-states.

Reader: state-subtree (instance)
Writer: (setf state-subtree) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

subtree.

Reader: terminal-class (instance)
Writer: (setf terminal-class) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

class.

Reader: terminal-gender (instance)
Writer: (setf terminal-gender) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

gender.

Function: terminal-p (object)
Package

earley-parser.

Source

object-representations.lisp.

Reader: terminal-word (instance)
Writer: (setf terminal-word) (instance)
Package

earley-parser.

Source

object-representations.lisp.

Target Slot

word.


Next: , Previous: , Up: Internals   [Contents][Index]

5.2.3 Generic functions

Generic Function: add-chart (chart chart-listing)
Package

earley-parser.

Methods
Method: add-chart ((chart chart) (chart-listing chart-listing))
Source

object-representations.lisp.

Generic Function: enqueue (state chart)
Package

earley-parser.

Methods
Method: enqueue ((state state) (chart chart))
Source

object-representations.lisp.

Generic Function: grammar-productions (non-terminal grammar)
Package

earley-parser.

Methods
Method: grammar-productions ((non-terminal string) (grammar grammar))
Source

object-representations.lisp.

Generic Function: incomplete? (state)
Package

earley-parser.

Methods
Method: incomplete? ((state state))

Return whether there is anything remaining of the subtree after the dot.

Source

object-representations.lisp.

Generic Function: lexicon-lookup (word lexicon)
Package

earley-parser.

Methods
Method: lexicon-lookup ((word string) (lexicon lexicon))
Source

object-representations.lisp.

Generic Function: next-cat (state)
Package

earley-parser.

Methods
Method: next-cat ((state state))

Return the next cathegory of ’state’

Source

object-representations.lisp.

Generic Function: predictor (state chart-listing grammar)
Package

earley-parser.

Methods
Method: predictor ((state state) (chart-listing chart-listing) (grammar grammar))

Predict possible successor states based on the grammar. As a side-effect, add these states to the chart that this state belong to.

Source

earley-parser.lisp.

Generic Function: scanner (state words chart-listing lexicon)
Package

earley-parser.

Methods
Method: scanner ((state state) (words list) (chart-listing chart-listing) (lexicon lexicon))

Check if the next category for this state is a member of the pos-categories for the current word. As a side effect, enqueue a new state corresponding to this find, into the current chart.

Source

earley-parser.lisp.

Generic Function: state->tree (state)
Package

earley-parser.

Methods
Method: state->tree ((state state))

Create a tree from a chart-listing object containting charts

Source

object-representations.lisp.


Previous: , Up: Internals   [Contents][Index]

5.2.4 Structures

Structure: chart
Package

earley-parser.

Source

object-representations.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: states
Readers

chart-states.

Writers

(setf chart-states).

Structure: chart-listing
Package

earley-parser.

Source

object-representations.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: charts
Readers

chart-listing-charts.

Writers

(setf chart-listing-charts).

Structure: grammar
Package

earley-parser.

Source

object-representations.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: rules
Initform

(make-hash-table :test earley-parser::*string-comparer*)

Readers

grammar-rules.

Writers

(setf grammar-rules).

Structure: lexicon
Package

earley-parser.

Source

object-representations.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: dictionary
Initform

(make-hash-table :test earley-parser::*string-comparer*)

Readers

lexicon-dictionary.

Writers

(setf lexicon-dictionary).

Slot: part-of-speech
Readers

lexicon-part-of-speech.

Writers

(setf lexicon-part-of-speech).

Structure: state
Package

earley-parser.

Source

object-representations.lisp.

Direct superclasses

structure-object.

Direct methods
Direct slots
Slot: condition
Package

common-lisp.

Type

string

Initform

(quote earley-parser::?)

Readers

state-condition.

Writers

(setf state-condition).

Slot: subtree
Readers

state-subtree.

Writers

(setf state-subtree).

Slot: dot
Initform

0

Readers

state-dot.

Writers

(setf state-dot).

Slot: constituent-index
Initform

0

Readers

state-constituent-index.

Writers

(setf state-constituent-index).

Slot: dot-index
Initform

0

Readers

state-dot-index.

Writers

(setf state-dot-index).

Slot: source-states
Readers

state-source-states.

Writers

(setf state-source-states).

Structure: terminal
Package

earley-parser.

Source

object-representations.lisp.

Direct superclasses

structure-object.

Direct slots
Slot: class
Package

common-lisp.

Readers

terminal-class.

Writers

(setf terminal-class).

Slot: gender
Readers

terminal-gender.

Writers

(setf terminal-gender).

Slot: word
Readers

terminal-word.

Writers

(setf terminal-word).


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.2 Functions

Jump to:   (  
A   C   E   F   G   I   L   M   N   P   R   S   T  
Index Entry  Section

(
(setf chart-listing-charts): Private ordinary functions
(setf chart-states): Private ordinary functions
(setf grammar-rules): Private ordinary functions
(setf lexicon-dictionary): Private ordinary functions
(setf lexicon-part-of-speech): Private ordinary functions
(setf state-condition): Private ordinary functions
(setf state-constituent-index): Private ordinary functions
(setf state-dot): Private ordinary functions
(setf state-dot-index): Private ordinary functions
(setf state-source-states): Private ordinary functions
(setf state-subtree): Private ordinary functions
(setf terminal-class): Private ordinary functions
(setf terminal-gender): Private ordinary functions
(setf terminal-word): Private ordinary functions

A
add-chart: Private generic functions
add-chart: Private generic functions

C
chart-listing->trees: Public generic functions
chart-listing->trees: Public generic functions
chart-listing-charts: Private ordinary functions
chart-listing-p: Private ordinary functions
chart-p: Private ordinary functions
chart-states: Private ordinary functions
completer: Private ordinary functions
copy-chart: Private ordinary functions
copy-chart-listing: Private ordinary functions
copy-grammar: Private ordinary functions
copy-lexicon: Private ordinary functions
copy-state: Private ordinary functions
copy-terminal: Private ordinary functions

E
earley-parse: Public ordinary functions
enqueue: Private generic functions
enqueue: Private generic functions

F
Function, (setf chart-listing-charts): Private ordinary functions
Function, (setf chart-states): Private ordinary functions
Function, (setf grammar-rules): Private ordinary functions
Function, (setf lexicon-dictionary): Private ordinary functions
Function, (setf lexicon-part-of-speech): Private ordinary functions
Function, (setf state-condition): Private ordinary functions
Function, (setf state-constituent-index): Private ordinary functions
Function, (setf state-dot): Private ordinary functions
Function, (setf state-dot-index): Private ordinary functions
Function, (setf state-source-states): Private ordinary functions
Function, (setf state-subtree): Private ordinary functions
Function, (setf terminal-class): Private ordinary functions
Function, (setf terminal-gender): Private ordinary functions
Function, (setf terminal-word): Private ordinary functions
Function, chart-listing-charts: Private ordinary functions
Function, chart-listing-p: Private ordinary functions
Function, chart-p: Private ordinary functions
Function, chart-states: Private ordinary functions
Function, completer: Private ordinary functions
Function, copy-chart: Private ordinary functions
Function, copy-chart-listing: Private ordinary functions
Function, copy-grammar: Private ordinary functions
Function, copy-lexicon: Private ordinary functions
Function, copy-state: Private ordinary functions
Function, copy-terminal: Private ordinary functions
Function, earley-parse: Public ordinary functions
Function, grammar-p: Private ordinary functions
Function, grammar-rules: Private ordinary functions
Function, lexicon-dictionary: Private ordinary functions
Function, lexicon-p: Private ordinary functions
Function, lexicon-part-of-speech: Private ordinary functions
Function, load-bnf-grammar: Public ordinary functions
Function, load-lexicon: Public ordinary functions
Function, make-chart: Private ordinary functions
Function, make-chart-listing: Private ordinary functions
Function, make-grammar: Private ordinary functions
Function, make-lexicon: Private ordinary functions
Function, make-state: Private ordinary functions
Function, make-terminal: Private ordinary functions
Function, read-lexicon-line: Private ordinary functions
Function, read-next-bnf-lexeme: Private ordinary functions
Function, read-next-bnf-production: Private ordinary functions
Function, state-condition: Private ordinary functions
Function, state-constituent-index: Private ordinary functions
Function, state-dot: Private ordinary functions
Function, state-dot-index: Private ordinary functions
Function, state-p: Private ordinary functions
Function, state-source-states: Private ordinary functions
Function, state-subtree: Private ordinary functions
Function, terminal-class: Private ordinary functions
Function, terminal-gender: Private ordinary functions
Function, terminal-p: Private ordinary functions
Function, terminal-word: Private ordinary functions

G
Generic Function, add-chart: Private generic functions
Generic Function, chart-listing->trees: Public generic functions
Generic Function, enqueue: Private generic functions
Generic Function, grammar-productions: Private generic functions
Generic Function, incomplete?: Private generic functions
Generic Function, lexicon-lookup: Private generic functions
Generic Function, next-cat: Private generic functions
Generic Function, predictor: Private generic functions
Generic Function, scanner: Private generic functions
Generic Function, state->tree: Private generic functions
grammar-p: Private ordinary functions
grammar-productions: Private generic functions
grammar-productions: Private generic functions
grammar-rules: Private ordinary functions

I
incomplete?: Private generic functions
incomplete?: Private generic functions

L
lexicon-dictionary: Private ordinary functions
lexicon-lookup: Private generic functions
lexicon-lookup: Private generic functions
lexicon-p: Private ordinary functions
lexicon-part-of-speech: Private ordinary functions
load-bnf-grammar: Public ordinary functions
load-lexicon: Public ordinary functions

M
make-chart: Private ordinary functions
make-chart-listing: Private ordinary functions
make-grammar: Private ordinary functions
make-lexicon: Private ordinary functions
make-state: Private ordinary functions
make-terminal: Private ordinary functions
Method, add-chart: Private generic functions
Method, chart-listing->trees: Public generic functions
Method, enqueue: Private generic functions
Method, grammar-productions: Private generic functions
Method, incomplete?: Private generic functions
Method, lexicon-lookup: Private generic functions
Method, next-cat: Private generic functions
Method, predictor: Private generic functions
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, print-object: Public standalone methods
Method, scanner: Private generic functions
Method, state->tree: Private generic functions

N
next-cat: Private generic functions
next-cat: Private generic functions

P
predictor: Private generic functions
predictor: Private generic functions
print-object: Public standalone methods
print-object: Public standalone methods
print-object: Public standalone methods

R
read-lexicon-line: Private ordinary functions
read-next-bnf-lexeme: Private ordinary functions
read-next-bnf-production: Private ordinary functions

S
scanner: Private generic functions
scanner: Private generic functions
state->tree: Private generic functions
state->tree: Private generic functions
state-condition: Private ordinary functions
state-constituent-index: Private ordinary functions
state-dot: Private ordinary functions
state-dot-index: Private ordinary functions
state-p: Private ordinary functions
state-source-states: Private ordinary functions
state-subtree: Private ordinary functions

T
terminal-class: Private ordinary functions
terminal-gender: Private ordinary functions
terminal-p: Private ordinary functions
terminal-word: Private ordinary functions

Jump to:   (  
A   C   E   F   G   I   L   M   N   P   R   S   T  

Previous: , Up: Indexes   [Contents][Index]

A.4 Data types

Jump to:   C   D   E   F   G   L   O   P   S   T  
Index Entry  Section

C
chart: Private structures
chart-listing: Private structures
cl-earley-parser: The cl-earley-parser system
cl-earley-parser.asd: The cl-earley-parser/cl-earley-parser․asd file

D
defpackage.lisp: The cl-earley-parser/defpackage․lisp file

E
earley-parser: The earley-parser package
earley-parser.lisp: The cl-earley-parser/earley-parser․lisp file

F
File, cl-earley-parser.asd: The cl-earley-parser/cl-earley-parser․asd file
File, defpackage.lisp: The cl-earley-parser/defpackage․lisp file
File, earley-parser.lisp: The cl-earley-parser/earley-parser․lisp file
File, grammar-reader.lisp: The cl-earley-parser/grammar-reader․lisp file
File, object-representations.lisp: The cl-earley-parser/object-representations․lisp file

G
grammar: Private structures
grammar-reader.lisp: The cl-earley-parser/grammar-reader․lisp file

L
lexicon: Private structures

O
object-representations.lisp: The cl-earley-parser/object-representations․lisp file

P
Package, earley-parser: The earley-parser package

S
state: Private structures
Structure, chart: Private structures
Structure, chart-listing: Private structures
Structure, grammar: Private structures
Structure, lexicon: Private structures
Structure, state: Private structures
Structure, terminal: Private structures
System, cl-earley-parser: The cl-earley-parser system

T
terminal: Private structures

Jump to:   C   D   E   F   G   L   O   P   S   T