Class Parser

A parser instance must have a grammar at instance creation time. The terminals, productions, and start_cat for the grammar are stored upon creation.

Parameters:

• string - A string. The string to be parsed. Immediately converted to a [WordList].by self.legal_input.

Returns:

The result of calling recurse_recognize on the start-cat, the empty agenda, and the wordlist generated from string.

Parse wordlist using goals (derivation). Return true if current grammar accepts wordlist. Else False.

Return True whenever goals and wordlist are empty.

Suppose goals is non-empty:

If goals[0] is a nonterminal, call expand (expand it with the grammar and continue parsing recursively). If goals[0] is a terminal then call match_word (try to match the next word and continue parsing). Both expand and match_word contain recursive calls to recurse_recognize.

Suppose goals is empty:

Parameters:

• goals - A list of categories and/or words proposed to cover wordlist, a partial derivation from the grammar.
• agenda - A list of ParserStates: each a pair of ([GoalList],[WordList])
• wordlist - a list of words.

Parameters:

• next_goal - grammar nonterminal
• rest_goals - other gramar elements from the same gramar production
• agenda - list of parser states.
• wordlist - list of words (strings).

next_goal is a terminal.

Suppose wordlist is non-empty:

If next_goal matches wordlist[0], keep parsing with rest_goals, agenda and wordlist[1:].

Else this parse path fails; call backtrack (if agenda is non-empty, continue parsing with the next parser state on agenda, and if agenda is empty, <Return>: False)

Suppose wordlist is empty.

Parameters:

• next_goal - grammar preterminal
• wordlist - list of words (strings).
• rest_goals - other gramar elements from the same gramar production
• agenda - list of parser states.

Suppose agenda is non-empty:

 agenda[0].GoalList = new goals
 agenda[0].WordList = new wordlist

Keep parsing with new goals and new worldlist and popped agenda.

Suppose agenda is empty