The parser generator is accessed by the macro defparser. After the name, of the parser, the macro form specifies the reduction rules and semantic actions for the grammar.
The rules specified in a defparser form are of three types, normal rules, error rules and combined-rules, described below.
Each normal rule corresponds to one production of the grammar to be parsed:
((non-terminal {grammar-symbol}*) {form}*)
The non-terminal is the left-hand side of the grammar production and the list of grammar-symbols defines the right-hand side of the production. (The right-hand side may be empty.) These grammar symbols must be either (grammar) tokens as returned by the lexer or non-terminals. The list of forms specifies the semantic action to be taken when the reduction is made by the parser. These forms may contain references to the variables $1 … $n, where n is the length of the right hand side of the production. When the reduction is done, these variables are bound to the semantic values corresponding to the grammar symbols of the rule.
If a grammar contains the production:
expression -> expression operator expression
with a semantic representation of a list of the individual semantic values, the Lisp grammar would contain the rule:
((expression expression operator expression) (list $1 $2 $3))
Error productions of the form:
((nt :error) ...some error behavior...)
are explained in the section below.
The first rule of the grammar should be of the form:
((nt nt1) $1)
where the non-terminal nt has no other productions and nt1 serves as the main "top-level" non-terminal.
The combined-rule clause is a way to group multiple normal-rule or error-rule clauses for the same non-terminal. For example, this single combined-rule clause:
(constant ((:FLOAT-CONSTANT) $1) ((:INTEGER-CONSTANT) $1))
is equivalent to these two normal-rule clauses:
((constant :FLOAT-CONSTANT) $1) ((constant :INTEGER-CONSTANT) $1)
If the grammar is ambiguous, there is conflict between rules of the grammar: either between reducing with two different rules or between reducing by a rule and shifting an input symbol. Such a conflict is resolved at parser generation time by selecting the highest priority action, where the priority of a reduce action is determined by the closeness of the rule to the beginning of the grammar. A priority is assigned to a shift by associating it with the rule that results in the shift being performed.
For example, if the grammar contains the two rules:
:if expression :then statement :else statement.:if expression :then statement.
this results in a conflict in the parser between a shift of :else, for rule a, and a reduce by rule b. This conflict may be resolved by listing rule a earlier in the grammar than rule b. This ensures that the shift is always done.
Note that ambiguities cannot always be resolved successfully in this way. In this example, if the ambiguity is resolved the other way around, by listing rule b first, this results in the if … then … part of an if … then … else … statement being reduced, and a syntax error is produced for the else part.
During parser generation, any conflicts between rules are reported, together with information about how the conflict was resolved.
LispWorks® User Guide and Reference Manual - 01 Dec 2021 19:30:23