CFG Table Output Syntax

From FSL
Jump to: navigation, search

The CFG table output, which consists of the Action and the Goto tables, may be easier to understand if one is already familiar with LR parsing. An LR parser algorithm can be found on Wikipedia. (Note that the Wikipedia algorithm uses a different format for reductions; our format allows us to forgo including the original list of productions by encoding the necessary information in the Action table rather than referring to the list of productions from the Action table.) The CFG Monitoring algorithm, which uses these tables, is explained here.

The Action table represents the actions to be taken when a given event is seen. The numbers down the left most column are the state, the columns represent the events seen (the top row). $ is the end of input event that we insert after every event for monitoring purposes.

  • shift(Num) represents pushing Num on the stack.
  • reduce(NonTerminal, Num) represents a reduction by the non-terminal NonTerminal. Num states are popped from the stack, the state at the top of the stack after popping and NonTerminal are used as input to the Goto table. The result from Goto is pushed on the stack.
  • accept represents a state in which the input has been verified (note that it is always listed under the $ event).
  • error represents an error condition in the table.

The Goto table is used after a reduction to decide which state to transition to. The Action table is always consulted first, if the action is reduce(NonTerminal, Num), Num states are popped from the stack. The NonTerminal and state at the top of the stack, after popping, are used to find the proper entry in the Goto table.

  • num represents the state to transition to.
  • error represents an error condition in the table.

Conflicts, if any, are also output (together with their canonical LR(1) collections) by the CFG plugin. Conflicts are represented as pairs <conflict_type | state> where conflict_type is shift-reduce or reduce-reduce. shift-reduce conflicts are resolved in favor of shift, reduce-reduce are resolved arbitrarily. A state can be found in the canonical collection by looking for the proper number surrounded by [[]]. In a canonical collection, the current cursor position is marked by *; between the conflict list and the collection one can diagnose the reasons for a particular conflict.

Example

For the grammar:

event a 
event b
cfg:  S -> b S b | b A b | epsilon, 
      A -> A a | a

The output, which denotes a shift-reduce conflict in state 7, is:

Action
  $ a b
0 error error shift(5)
1 error reduce(A, 1) reduce(A, 1)
2 error reduce(A, 2) reduce(A, 2)
3 error shift(2) shift(9)
4 error shift(2) shift(10)
5 error shift(1) shift(6)
6 reduce(S, 2) shift(1) shift(7)
7 error shift(1) shift(7)
8 accept error error
9 reduce(S, 3) error error
10 error error reduce(S, 3)
11 error error shift(13)
12 error error shift(14)
13 reduce(S, 3) error error
14 error error reduce(S, 3)
Goto
  A S
0 error 8
1 error error
2 error error
3 error error
4 error error
5 3 11
6 4 12
7 4 12
8 error error
9 error error
10 error error
11 error error
12 error error
13 error error
14 error error
 

conflictList(
  < shift-reduce | 7 >) 
collection(
  [[[0]][
     {S -> * S $,$},
     {S -> * b b,$},
     {S -> * b A b,$},
     {S -> * b S b,$}]]
  ; 
  [[[1]][
     {A -> a *,a},
     {A -> a *,b}]]
  ; 
  [[[2]][
     {A -> A a *,a},
     {A -> A a *,b}]]
  ; 
  [[[3]][
     {A -> A * a,a},
     {A -> A * a,b},
     {S -> b A * b,$}]]
  ; 
  [[[4]][
     {A -> A * a,a},
     {A -> A * a,b},
     {S -> b A * b,b}]]
  ; 
  [[[5]][
     {A -> * a,a},
     {A -> * a,b},
     {A -> * A a,a},
     {A -> * A a,b},
     {S -> * b b,b},
     {S -> b * b,$},
     {S -> * b A b,b},
     {S -> * b S b,b},
     {S -> b * A b,$},
     {S -> b * S b,$}]]
  ; 
  [[[6]][
     {A -> * a,a},
     {A -> * a,b},
     {A -> * A a,a},
     {A -> * A a,b},
     {S -> * b b,b},
     {S -> b * b,b},
     {S -> b b *,$},
     {S -> * b A b,b},
     {S -> * b S b,b},
     {S -> b * A b,b},
     {S -> b * S b,b}]]
  ; 
  [[[7]][
     {A -> * a,a},
     {A -> * a,b},
     {A -> * A a,a},
     {A -> * A a,b},
     {S -> * b b,b},
     {S -> b * b,b},
     {S -> b b *,b},
     {S -> * b A b,b},
     {S -> * b S b,b},
     {S -> b * A b,b},
     {S -> b * S b,b}]]
  ; 
  [[[8]][
     {S -> S * $,$}]]
  ; 
  [[[9]][
     {S -> b A b *,$}]]
  ; 
  [[[10]][
     {S -> b A b *,b}]]
  ; 
  [[[11]][
     {S -> b S * b,$}]]
  ; 
  [[[12]][
     {S -> b S * b,b}]]
  ; 
  [[[13]][
     {S -> b S b *,$}]]
  ; 
  [[[14]][
     {S -> b S b *,b}]]
) 

Personal tools
Namespaces

Variants
Actions
Navigation