Как использовать таблицу разбора и составлять карту pu sh в парсере, управляемом таблицей?

Question

Я пишу компилятор, используя нисходящий табличный анализ. Я преобразовал мою грамматику в 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'

Используя инструмент здесь , я сгенерировал таблицу разбора и стек pu sh карта, которая следующая:

Таблица разбора:

[[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]]

Pu sh карта:

{"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]} 

Конструкция таблицы синтаксического анализа дается как следующее:

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), сгенерированные для этой грамматики, не могут быть точными.

Однако, для чего это стоит, вот мой реверс-инжиниринг этих таблиц. Вероятно, вы могли бы глубже понять эту процедуру, прочитав учебник , на который ссылается инструмент . ( Примечание: ссылка , а не как подтверждение, ни книги, ни поставщика. Я только что скопировал ее из инструмента.)

Символы терминала появляются в верхнем ряду таблицы разбора в порядке (тот, который, как говорится в инструкциях, должен быть удален для использования). Таким образом, символ терминала 1 равен ',', символ 2 - '+' и т. Д. До символа 46, который является $, обычно используемым в качестве маркера окончания ввода. (Это отличается от '$', который был бы буквальным знаком доллара.)

Нетерминальные символы не отображаются явно (поэтому вы не можете восстановить их имена из таблиц), но они также нумеруются в целях. Их 54, и каждая строка таблицы разбора (после первых двух) соответствует нетерминальному символу.

В Прогнозе перечислены 110 произведений, которые перечислены (с соответствующим индексом) установить секцию вывода этого инструмента. Каждое производство соответствует одной записи в «карте pu sh», которая (по неизвестным мне причинам) использует преобразование строки производственного номера в качестве ключа.

Соответствующее значение в pu sh map - это список индексов: отрицательные индексы относятся к терминалам, а положительные индексы относятся к нетерминалам. Индекс 0 не используется, поэтому строка 0 карты анализа не используется. Из этих индексов можно реконструировать правую часть производства, но они фактически используются для указания того, что положить sh в стек разбора на каждом шаге разбора.

Стек содержит список текущих прогнозов, причем верхний элемент стека является непосредственным прогнозом на данный момент в разборе.

Таким образом, алгоритм выглядит следующим образом:

1. Initialize стек синтаксического анализатора до [1, -46], который указывает, что текущий прогноз состоит из правой части производства <START> -> <prog>, за которым следует маркер конца ввода $.

2. Повторяйте следующее до тех пор, пока не прекратите из-за ошибки или принятия:

   1. Если вершина стека отрицательна:
      • Если токен предпросмотра имеет соответствующий номер токена (то есть (абсолютное значение вершины стека), затем вытолкните стек и примите маркер предварительного просмотра. Если этот токен является индикатором конца ввода, то анализ завершен, и ввод был действительным. В противном случае новый токен lookahead является следующим входным токеном.
      • Если токен lookahead не соответствует вершине стека, значит, ввод неправильный. Сообщить об ошибке и прекратить анализ.
   2. Если вершина стека положительна:
      • Получить значение rhs из parseTable[stack.top()][lookahead]. Если rhs имеет значение, превышающее количество произведений (в данном случае это значения 111 или 112), то ввод неправильный. Сообщить об ошибке и прекратить анализ. (Это значение скажет вам, была ли это ошибка сканирования или всплывающая ошибка, но это может не иметь большого значения для вас. Оно может быть использовано для улучшения отчетов об ошибках.)
      • Извлечение стека разбора и pu sh элементы из pushMap[rhs] в стек, начиная с конца. (Например, если бы rhs было 4, вы бы использовали список из pushMap["4"], то есть [10, -1]. Таким образом, вы должны вначале положить sh -1, а затем 10 в стек анализатора.)
      • Для карты pu sh, созданной инструментом взлома, кажется, что в pushMap не будет записей для ε с правой стороны. Так что если pushMap[rhs] не существует, вы просто извлекаете стек разбора; нет ничего пу sh.

Этот алгоритм не включает в себя какую-либо процедуру для создания синтаксического дерева для успешного анализа. Но если вы хотите сделать что-то большее, чем просто решить, является ли ввод действительной программой или нет, то вам определенно нужно создать какое-то синтаксическое дерево.

---

Примечание: грамматика не является LL (1) поэтому таблицы синтаксического анализа неверны.

Я не знаю, сколько доверия вы должны дать инструменту, который вы используете.

Ваша грамматика не LL (1), но инструмент не дает никаких указаний на этот факт.

Простой пример -

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

, где маркер предпросмотра [ не предсказывает уникальное производство. Это было бы легко исправить с помощью левого факторинга, но я не вижу никаких доказательств того, что инструмент способен на это.

Более серьезная проблема -

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

Поскольку relExpr может начинаться с arithExpr, два производства для expr перекрываются; Невозможно предсказать из проверки одного жетона предпросмотра (или даже любого постоянного числа жетонов предвкушения), является ли expr сравнением или нет. Вы не можете сказать, пока не закончите sh синтаксический анализ начального арифметического c выражения (которое может иметь произвольную длину).

Если вы настаиваете на LL (1), вам нужно будет сделать что-то вроде :

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

Более того, expr приводит к factor, который может быть либо variable, либо functionCall, оба из которых начинаются с idnest (что в конечном итоге приводит к терминалу id). Но это еще не вся история, потому что вы можете встретить последовательность <id> '(' <aParams> ')' как в idnest, так и в functionCall.

Возможно, этот инструмент не собирается сообщать вам, что ваша грамматика не является LL (1), но мне кажется, что в этом случае он не должен генерировать таблицы, поскольку таблицы обязательно вводят в заблуждение. Конфликты прогнозирования означают, что таблица синтаксического анализа должна отдавать предпочтение тому или иному конкурирующему производству, и тот, который он не предпочитает, не может появляться в разборе, в результате чего действительные входные данные будут отклонены.

Я считаю, что можно создать грамматику LL (1) для этого языка, но, честно говоря, она не кажется мне лучшей стратегией. В грамматике уже так много нетерминалов бухгалтерского учета, что она граничит с нечитаемым. Если вы настаиваете на нисходящем парсере, используйте генератор, который позволяет «расширенным» BNF: операторы повторения и опциональности справа. В качестве альтернативы, вы можете использовать генератор LALR (1) с очень упрощенной грамматикой, поскольку LALR (1) допускает как левые рекурсии, так и левые необработанные произведения.