Ist die Reihenfolge der Reduktion in Yacc definiert?

Question

Dies ist eher eine "im Prinzip" als eine praktische Frage. Ist die Reihenfolge, in der Yacc Produktionen reduziert, und liest neue Token aus dem definierten Lexer. Das heißt, wenn ich den folgenden Satz von Token hatte:

INTEGER_BEGIN 
INTEGER_VALUE 
LESS_THAN 
INTEGER_BEGIN 
INTEGER_VALUE 

Kann Yacc, im Rahmen ihrer Semantik, lesen Sie die LESS_THAN Token aus dem Lexer, bevor es INTEGER BEGIN INTEGER_VALUE auf eine einzige Sache reduziert, da eine Reihe von Produktionen wie:

expr : expr LESS_THAN expr 
    | integer 

integer : INTEGER_BEGIN INTEGER_VALUE 

Machen Sie die Regeln für diese Änderung, wenn diese mit semantischen Aktionen definiert sind?

Answer 1

Ja kann es. Yacc erstellt einen LALR (1) -Parser - das (1) bedeutet 1 Token von Lookahead - so dass es 1 Token nach dem Ende der Token für eine Regel vorlesen kann, bevor diese Regel reduziert wird. Die Existenz von semantischen Aktionen ist irrelevant, da die semantische Aktion nur ein C-Code ist, der ausgeführt wird, bevor eine Regel reduziert wird.

Beachten Sie, dass es keine Garantie gibt, dass IMMER ein Token voraus gelesen wird. Der Parser, der von yacc oder bison erstellt wird, verwendet manchmal 'standardmäßige Reduktionen' - Zustände, in denen eine Regel reduziert werden kann, OHNE dass zuerst das nächste Token gelesen werden muss. Dies geschieht immer dann, wenn die Reduktion einer Regel unabhängig vom nächsten Token ist. In diesem speziellen Beispiel könnte eine Standardreduktion für die integer-Regel verwendet werden, so dass sie ohne Lookahead reduziert werden kann, aber auch hier gibt es keine Garantie - Standardreduzierungen sind eine Optimierung, die von einigen (aber nicht allen) Implementierungen von verwendet wird yacc.