如何在 table 驱动的解析器中使用解析 table 和堆栈推送映射？

Question

我正在编写一个编译器，使用自上而下 table 驱动的解析。我已经将语法转换为 LL(1)，如下所示：

<START> -> <prog> 

<aParams> -> <expr> <rept-aParams1> 
<aParams> -> EPSILON 

<aParamsTail> -> ',' <expr> 

<addOp> -> '+' 
<addOp> -> '-' 
<addOp> -> 'or' 

<arithExpr> -> <term> <rightrec-arithExpr> 

<arraySize> -> '[' 'intNum' ']' 
<arraySize> -> '[' ']' 

<assignOp> -> '=' 

<assignStat> -> <variable> <assignOp> <expr> 

<classDecl> -> 'class' 'id' <opt-classDecl2> '{' <rept-classDecl4> '}' ';' 

<expr> -> <arithExpr> 
<expr> -> <relExpr> 

<fParams> -> <type> 'id' <rept-fParams2> <rept-fParams3> 
<fParams> -> EPSILON 

<fParamsTail> -> ',' <type> 'id' <rept-fParamsTail3> 

<factor> -> <variable> 
<factor> -> <functionCall> 
<factor> -> 'intNum' 
<factor> -> 'floatNum' 
<factor> -> '(' <arithExpr> ')' 
<factor> -> 'not' <factor> 
<factor> -> <sign> <factor> 

<funcBody> -> <opt-funcBody0> 'do' <rept-funcBody2> 'end' 

<funcDecl> -> 'id' '(' <fParams> ')' ':' <type> ';' 
<funcDecl> -> 'id' '(' <fParams> ')' ':' 'void' ';' 

<funcDef> -> <funcHead> <funcBody> ';' 

<funcHead> -> <opt-funcHead0> 'id' '(' <fParams> ')' ':' <type> 
<funcHead> -> <opt-funcHead0> 'id' '(' <fParams> ')' ':' 'void' 

<functionCall> -> <rept-functionCall0> 'id' '(' <aParams> ')' 

<idnest> -> 'id' <rept-idnest1> '.' 
<idnest> -> 'id' '(' <aParams> ')' '.' 

<indice> -> '[' <arithExpr> ']' 

<memberDecl> -> <funcDecl> 
<memberDecl> -> <varDecl> 

<multOp> -> '*' 
<multOp> -> '/' 
<multOp> -> 'and' 

<opt-classDecl2> -> 'inherits' 'id' <rept-opt-classDecl22> 
<opt-classDecl2> -> EPSILON 

<opt-funcBody0> -> 'local' <rept-opt-funcBody01> 
<opt-funcBody0> -> EPSILON 

<opt-funcHead0> -> 'id' 'sr' 
<opt-funcHead0> -> EPSILON 

<prog> -> <rept-prog0> <rept-prog1> 'main' <funcBody> 

<relExpr> -> <arithExpr> <relOp> <arithExpr> 

<relOp> -> 'eq' 
<relOp> -> 'neq' 
<relOp> -> 'lt' 
<relOp> -> 'gt' 
<relOp> -> 'leq' 
<relOp> -> 'geq' 

<rept-aParams1> -> <aParamsTail> <rept-aParams1> 
<rept-aParams1> -> EPSILON 

<rept-classDecl4> -> <visibility> <memberDecl> <rept-classDecl4> 
<rept-classDecl4> -> EPSILON 

<rept-fParams2> -> <arraySize> <rept-fParams2> 
<rept-fParams2> -> EPSILON 

<rept-fParams3> -> <fParamsTail> <rept-fParams3> 
<rept-fParams3> -> EPSILON 

<rept-fParamsTail3> -> <arraySize> <rept-fParamsTail3> 
<rept-fParamsTail3> -> EPSILON 

<rept-funcBody2> -> <statement> <rept-funcBody2> 
<rept-funcBody2> -> EPSILON 

<rept-functionCall0> -> <idnest> <rept-functionCall0> 
<rept-functionCall0> -> EPSILON 

<rept-idnest1> -> <indice> <rept-idnest1> 
<rept-idnest1> -> EPSILON 

<rept-opt-classDecl22> -> ',' 'id' <rept-opt-classDecl22> 
<rept-opt-classDecl22> -> EPSILON 

<rept-opt-funcBody01> -> <varDecl> <rept-opt-funcBody01> 
<rept-opt-funcBody01> -> EPSILON 

<rept-prog0> -> <classDecl> <rept-prog0> 
<rept-prog0> -> EPSILON 

<rept-prog1> -> <funcDef> <rept-prog1> 
<rept-prog1> -> EPSILON 

<rept-statBlock1> -> <statement> <rept-statBlock1> 
<rept-statBlock1> -> EPSILON 

<rept-varDecl2> -> <arraySize> <rept-varDecl2> 
<rept-varDecl2> -> EPSILON 

<rept-variable0> -> <idnest> <rept-variable0> 
<rept-variable0> -> EPSILON 

<rept-variable2> -> <indice> <rept-variable2> 
<rept-variable2> -> EPSILON 

<rightrec-arithExpr> -> EPSILON 
<rightrec-arithExpr> -> <addOp> <term> <rightrec-arithExpr> 

<rightrec-term> -> EPSILON 
<rightrec-term> -> <multOp> <factor> <rightrec-term> 

<sign> -> '+' 
<sign> -> '-' 

<statBlock> -> 'do' <rept-statBlock1> 'end' 
<statBlock> -> <statement> 
<statBlock> -> EPSILON 

<statement> -> <assignStat> ';' 
<statement> -> 'if' '(' <relExpr> ')' 'then' <statBlock> 'else' <statBlock> ';' 
<statement> -> 'while' '(' <relExpr> ')' <statBlock> ';' 
<statement> -> 'read' '(' <variable> ')' ';' 
<statement> -> 'write' '(' <expr> ')' ';' 
<statement> -> 'return' '(' <expr> ')' ';' 
<statement> -> <functionCall> ';' 

<term> -> <factor> <rightrec-term> 

<type> -> 'integer' 
<type> -> 'float' 
<type> -> 'id' 

<varDecl> -> <type> 'id' <rept-varDecl2> ';' 

<variable> -> <rept-variable0> 'id' <rept-variable2> 

<visibility> -> 'public' 
<visibility> -> 'private'

使用工具here，我生成了一个parse table和stack push map，如下：

解析Table:

[[0,"','","'+'","'-'","'or'","'['","'intNum'","']'","'='","'class'","'id'","'{'","'}'","';'","'floatNum'","'('","')'","'not'","'do'","'end'","':'","'void'","'.'","'*'","'/'","'and'","'inherits'","'local'","'sr'","'main'","'eq'","'neq'","'lt'","'gt'","'leq'","'geq'","'if'","'then'","'else'","'while'","'read'","'write'","'return'","'integer'","'float'","'public'","'private'","$"],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,112,112,112,112,112,112,112,112,1,1,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,1,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111],[0,112,2,2,112,112,2,112,112,112,2,112,112,112,2,2,3,2,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,4,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,5,6,7,112,111,112,112,112,111,112,112,112,111,111,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,111,8,8,112,112,8,111,112,112,8,112,112,111,8,8,111,8,112,112,112,112,112,112,112,112,112,112,112,112,111,111,111,111,111,111,112,112,112,112,112,112,112,112,112,112,112,112],[0,111,112,112,112,10,112,112,112,112,112,112,112,111,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,111,111,112,112,111,112,11,112,111,112,112,112,111,111,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,12,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,13,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,111,15,15,112,112,15,112,112,112,15,112,112,111,15,15,111,15,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,16,112,112,112,112,112,17,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,16,16,112,112,112],[0,18,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,111,25,25,111,112,21,111,112,112,20,112,112,111,22,23,111,24,112,112,112,112,112,111,111,111,112,112,112,112,111,111,111,111,111,111,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,112,112,112,111,112,112,112,112,26,112,112,112,112,112,112,112,112,26,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111],[0,112,112,112,112,112,112,112,112,112,28,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111,111,112],[0,112,112,112,112,112,112,112,112,112,29,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,31,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,111,111,111,111,112,112,111,112,112,32,112,112,111,112,112,111,112,112,112,112,112,112,111,111,111,112,112,112,112,111,111,111,111,111,111,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,34,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,111,111,111,111,35,112,111,111,112,112,112,112,111,112,112,111,112,112,112,112,112,111,111,111,111,112,112,112,112,111,111,111,111,111,111,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,37,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,37,37,111,111,112],[0,112,111,111,112,112,111,112,112,112,111,112,112,112,111,111,112,111,112,112,112,112,112,38,39,40,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,112,42,112,112,112,112,112,112,112,112,112,112,112,112,112,112,41,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,44,112,112,112,112,112,112,112,112,43,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,46,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,47,47,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,47,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111],[0,111,48,48,112,112,48,112,112,112,48,112,112,111,48,48,111,48,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,111,111,112,112,111,112,112,112,111,112,112,112,111,111,112,111,112,112,112,112,112,112,112,112,112,112,112,112,49,50,51,52,53,54,112,112,112,112,112,112,112,112,112,112,112,112],[0,55,112,112,112,112,112,112,112,112,112,112,112,112,112,112,56,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,112,112,58,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,57,57,112],[0,60,112,112,112,59,112,112,112,112,112,112,112,112,112,112,60,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,61,112,112,112,112,112,112,112,112,112,112,112,112,112,112,62,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,64,112,112,112,63,112,112,112,112,112,112,112,112,112,112,64,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,65,112,112,112,112,112,112,112,112,66,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,65,112,112,65,65,65,65,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,68,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,69,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,70,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,71,112,112,112,112,112,112,112,112,112,72,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,73,112,112,112,112,112,112,112,74,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,73,73,112,112,112],[0,112,112,112,112,112,112,112,112,75,76,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,76,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,77,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,78,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,79,112,112,112,112,112,112,112,112,80,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,79,112,112,79,79,79,79,112,112,112,112,112],[0,112,112,112,112,81,112,112,112,112,112,112,112,82,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,84,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,86,86,86,86,85,112,86,86,112,112,112,112,86,112,112,86,112,112,112,112,112,112,86,86,86,112,112,112,112,86,86,86,86,86,86,112,112,112,112,112,112,112,112,112,112,112,112],[0,87,88,88,88,112,112,87,112,112,112,112,112,87,112,112,87,112,112,112,112,112,112,112,112,112,112,112,112,112,87,87,87,87,87,87,112,112,112,112,112,112,112,112,112,112,112,112],[0,89,89,89,89,112,112,89,112,112,112,112,112,89,112,112,89,112,112,112,112,112,112,90,90,90,112,112,112,112,89,89,89,89,89,89,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,91,92,112,112,111,112,112,112,111,112,112,112,111,111,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,94,112,112,95,112,112,112,112,93,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,94,112,95,94,94,94,94,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,102,112,112,111,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,97,112,111,98,99,100,101,112,112,112,112,112],[0,111,103,103,111,112,103,111,112,112,103,112,112,111,103,103,111,103,112,112,112,112,112,112,112,112,112,112,112,112,111,111,111,111,111,111,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,106,112,112,111,112,112,112,112,111,112,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,104,105,112,112,112],[0,112,112,112,112,112,112,112,112,112,107,112,111,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,107,107,111,111,112],[0,111,111,111,111,112,112,111,111,112,108,112,112,111,112,112,111,112,112,112,112,112,112,111,111,111,112,112,112,112,111,111,111,111,111,111,112,112,112,112,112,112,112,112,112,112,112,112],[0,112,112,112,112,112,112,112,112,112,111,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,112,111,111,109,110,112]]

推图：

{"1":[26],"2":[29,10],"4":[10,-1],"5":[-2],"6":[-3],"7":[-4],"8":[45,50],"9":[-7,-6,-5],"10":[-7,-5],"11":[-8],"12":[10,7,53],"13":[-13,-12,30,-11,23,-10,-9],"14":[5],"15":[27],"16":[32,31,-10,51],"18":[33,-10,51,-1],"19":[53],"20":[18],"21":[-6],"22":[-14],"23":[-16,5,-15],"24":[13,-17],"25":[13,47],"26":[-19,34,-18,24],"27":[-13,51,-20,-16,11,-15,-10],"28":[-13,-21,-20,-16,11,-15,-10],"29":[-13,14,17],"30":[51,-20,-16,11,-15,-10,25],"31":[-21,-20,-16,11,-15,-10,25],"32":[-16,2,-15,-10,35],"33":[-22,36,-10],"34":[-22,-16,2,-15,-10],"35":[-7,5,-5],"36":[15],"37":[52],"38":[-23],"39":[-24],"40":[-25],"41":[37,-10,-26],"43":[38,-27],"45":[-28,-10],"47":[14,-29,40,39],"48":[5,28,5],"49":[-30],"50":[-31],"51":[-32],"52":[-33],"53":[-34],"54":[-35],"55":[29,3],"57":[30,21,54],"59":[31,6],"61":[32,12],"63":[33,6],"65":[34,49],"67":[35,19],"69":[36,20],"71":[37,-10,-1],"73":[38,52],"75":[39,9],"77":[40,16],"79":[41,49],"81":[42,6],"83":[43,19],"85":[44,20],"88":[45,50,4],"90":[46,13,22],"91":[-2],"92":[-3],"93":[-19,41,-18],"94":[49],"96":[-13,8],"97":[-13,48,-38,48,-37,-16,27,-15,-36],"98":[-13,48,-16,27,-15,-39],"99":[-13,-16,53,-15,-40],"100":[-13,-16,10,-15,-41],"101":[-13,-16,10,-15,-42],"102":[-13,18],"103":[46,13],"104":[-43],"105":[-44],"106":[-10],"107":[-13,42,-10,51],"108":[44,-10,43],"109":[-45],"110":[-46]}

解析table的构造如下：

On the LL(1) Parsing Table's Meaning and Construction

    The top row corresponds to the columns for all the potential terminal symbols, augmented with $ to represent the end of the parse.
    The leftmost column and second row are all zero filled, to accomodate the way Fischer and LeBlanc wrote their parser's handling of abs().
    The remaining rows correspond to production rules in the original grammar that you typed in.
    Each entry in that row maps the left-hand-side (LHS) of a production rule onto a line-number. That number is the line in which the LHS had that specific column symbol in its predict set.

    If a terminal is absent from a non-terminal's predict set, an error code is placed in the table. If that terminal is in follow(that non-terminal), the error is a POP error. Else, it's a SCAN error.

    POP error code = # of predict table productions + 1

    SCAN error code = # of predict table productions + 2

In practice, you'd want to tear the top, label row off of the table and stick it in a comment, so that you can make sense of your table. The remaining table can be used as is.

不过，鉴于这些，我并不完全确定如何进行。我只是好奇，给定这两个对象，通用算法是什么来解析令牌流并确定它在语法上是正确的。

Answer 1

这对您没有多大帮助，因为如下所述，为该语法生成的 LL(1) 解析 table 可能不准确。

然而，就其价值而言，这是我对那些 table 的逆向工程。通过阅读text book referenced by the tool，您可能会对这个过程有更深入的了解。（注：link不是背书，既不是书也不是供应商。我只是从工具中复制的。)

终端符号按顺序出现在解析的第一行table（说明中说应该删除的那个）。所以终结符号 1 是 ','，符号 2 是 '+'，依此类推直到符号 46，这是通常用作输入结束标记的 $。（这与 '$' 不同，后者是字面上的美元符号。）

非终结符号没有明确出现（因此您无法从 table 中恢复它们的名称）但它们也按顺序编号。其中有 54 个，解析的每一行 table（在前两个之后）对应一个非终端符号。

有 110 个产品，在该工具输出的预测集部分中列出（及其相应的索引）。每个生产对应“推图”中的一个条目，它（因为这是Javascript）使用生产编号的字符串转换作为键。

推图中对应的值是一个索引列表：负索引表示终端，正索引表示非终端。未使用索引 0，这就是解析图的第 0 行未使用的原因。从这些索引中，可以重建产生式的右侧，但它们实际上用于指示在解析的每个步骤将什么推入解析堆栈。

堆栈包含当前预测列表，堆栈的顶部元素是解析中此时的直接预测。

所以算法如下：

将解析器堆栈初始化为[1, -46]，这表明当前预测由产生式<START> -> <prog>的右侧和输入结束符组成标记 $.
重复以下操作，直到因错误或接受而终止：
1. 如果栈顶为负：
  - 如果lookahead token有对应的token号（即栈顶的绝对值），则出栈并接受lookahead token。如果该标记是输入结束指示符，则解析完成且输入有效。否则，新的先行标记是下一个输入标记。
  - 如果先行标记与栈顶不对应，则输入不正确。报错并终止解析。
2. 如果栈顶为正：
  - 从 parseTable[stack.top()][lookahead] 中检索值 rhs。如果 rhs 的值大于产生式的数量（在本例中为值 111 或 112），则输入不正确。报告错误并终止解析。（该值会告诉您它是扫描错误还是弹出错误，但这对您来说可能没有太大区别。它可用于改进错误报告。）
  - 弹出解析堆栈，并将 pushMap[rhs] 中的元素压入堆栈，从末尾开始。（例如，如果 rhs 为 4，您将使用 pushMap["4"] 中的列表，即 [10, -1]。因此您将首先推送 -1，然后推送 10到解析器堆栈。）
  - 对于hack-off工具生成的push-map，似乎pushMap中不会有ε右侧的条目。因此，如果 pushMap[rhs] 不存在，您只需弹出解析堆栈；没有什么可推的。

该算法不包括为成功解析生成语法树的任何过程。但是如果你想做的不仅仅是决定输入是否是一个有效的程序，那么你肯定想要生成某种语法树。

注意：语法不是 LL(1)，所以解析 table 是错误的。

我不知道你应该给你正在使用的工具多少可信度。

您的语法不是 LL(1)，但该工具没有提供任何表明这一事实的指示。

一个简单的例子是

<arraySize> -> '[' 'intNum' ']' 
<arraySize> -> '[' ']'

前瞻标记 [ 不预测独特的生产。这很容易通过左因式分解来解决，但我没有看到任何证据表明该工具能够做到这一点。

更严重的问题是

<expr>      -> <arithExpr> 
<expr>      -> <relExpr> 
<arithExpr> -> <term> <rightrec-arithExpr> 
<relExpr>   -> <arithExpr> <relOp> <arithExpr>

由于 relExpr 可以从 arithExpr 开始，因此 expr 的两个产生式重叠；不可能通过检查单个前瞻标记（或者实际上是任何固定数量的前瞻标记）来预测 expr 是否是比较。在完成对初始算术表达式（可以具有任意长度）的解析之前，您无法判断。

如果您坚持 LL(1)，则需要执行以下操作：

<expr> -> <arithExpr> <optional-relExpr-tail>
<optional_relExpr-tail> -> EPSILON
<optional_relExpr-tail> -> <relop> <arithExpr>

此外，expr 导致 factor，它可以是 variable 或 functionCall，两者都以 idnest 开头（这最终导致终端id）。但这也不是全部，因为您可能会在 idnest 和 functionCall.

中遇到序列 <id> '(' <aParams> ')'

也许那个工具并不打算告诉你你的语法不是 LL(1)，但在我看来它不应该在那种情况下生成 tables，因为 tables 必然具有误导性。预测冲突意味着解析 table 必须偏爱一个或另一个竞争产品，并且它不喜欢的任何一个都不能出现在解析中，结果有效输入将被拒绝。

<意见>

我相信可以为该语言创建 LL(1) 文法，但老实说，这在我看来并不是最佳策略。语法中已经有如此多的簿记非终结符，以至于它几乎无法阅读。如果您坚持使用自上而下的解析器，请使用允许“扩展”BNF 的生成器：右侧的重复和可选运算符。或者，您可以使用语法大大简化的 LALR(1) 生成器，因为 LALR(1) 允许左递归和左未分解的产生式。

如何在 table 驱动的解析器中使用解析 table 和堆栈推送映射？

How to use a parse table and stack push map in a table driven parser?

compiler-construction

注意：语法不是 LL(1)，所以解析 table 是错误的。