The LALR State Table is used by the LALR parser which analyzes the syntactic structure of a grammar. Essentially, it reads a series of tokens from the tokenizer (also called a scanner) and then determines when one of the rules are complete.
The following tags were added in Version 2.5 of the Builder.
##LALR-TABLE | ||
... | ||
[ | ##LALR-STATES | |
... | ||
[ | ##LALR-ACTIONS | |
... | ||
##END-LALR-ACTIONS | ] | |
... | ||
##END-LALR-STATES | ] | |
... | ||
##END-LALR-TABLE |
Name | Description |
---|---|
%Count% | The Count variable contains the number of states in the grammar's LALR State Table. This variable is useful for array declaration or setting the global variables before storing each of the actual rules. |
%InitialState% | This variable contains the numeric index of the initial state in the LALR State Table. |
Name | Description |
---|---|
%Delimiter% | For each edge in the state, this variable is set to the value set with the ##Delimiter tag. For the last item in the list, the value is set to a number of spaces. |
%ActionCount% | Each state contains one or more parse actions. |
%Index% | This variable contains the index of the state in the table. |
Name | Description |
---|---|
%Action% | In the Compiled Grammar Table file, each action is represented with a numeric constant. These are the same values that are used for the Action variable. The values are displayed below. |
%Action.Name% | This variable will contain a simple text description of each action. The values are displayed below. |
%Delimiter% | For each state in the table, this variable is set to the value set with the ##Delimiter tag. For the last item in the list, the value is set to a number of spaces. |
%SymbolIndex% | Each action is linked to a symbol. This variable contains the index of the symbol. |
%Value% | Depending on the value of the Action field, the target will hold different types of information. In the case of a reduce, the value will contain the index of the rule to be reduced. In the case of a shift or goto, the value will contain the target state. |
Value | Description | Description |
---|---|---|
1 | Shift | This action indicates the symbol is to be shifted. The Target field will contain the index of the state in the LALR State table that the parsing engine will advance to. |
2 | Reduce Rule | This action denotes that the parser can reduce a rule. The Target field will contain the index of the rule in the Rule Table. |
3 | Goto | This action is used when a rule is reduced and the parser jumps to the state that represents the shifted nonterminal. The Target field will contain the index of the state in the LALR State table that the parsing engine will jump to after a reduction if completed. |
4 | Accept | When the parser encounters the Accept action for a given symbol, the source text is accepted as correct and complete. In this case, the Target field is not needed and should be ignored. |
The following displays a template that will output the content of the LALR State Table using formatted text.
##LALR-TABLE |
Table Count: %Count% |
Initial State: %InitialState% |
##LALR-STATES |
State %Index% |
Action Count : %ActionCount% |
Actions: |
##LALR-ACTIONS |
Symbol %SymbolIndex% %Action.Name% %Value% |
##END-LALR-ACTIONS |
##END-LALR-STATES |
##END-LALR-TABLE |
If the "Simple" example grammar is used, the program template will create the following text for LALR State #4. The states before and after #4 were excluded for brevity.
Table Count: 59 |
Initial State: 0 |
. |
. |
. |
State 4 |
Action Count: 5 |
Actions: |
8 Shift 5 |
25 Shift 6 |
27 Shift 7 |
29 Shift 8 |
38 Goto 37 |