This is more of an "in principle" question than a practical one. Is the order in which Yacc reduces productions, and reads new tokens from the lexer defined. That is, if I had the following set of tokens:
INTEGER_BEGIN
INTEGER_VALUE
LESS_THAN
INTEGER_BEGIN
INTEGER_VALUE
Can Yacc, within its semantics, read the LESS_THAN
token from the lexer, before it reduces INTEGER BEGIN INTEGER_VALUE
to a single thing, given a set of productions like:
expr : expr LESS_THAN expr
| integer
integer : INTEGER_BEGIN INTEGER_VALUE
Do the rules for this change if these are defined with semantic actions?
Only the names and literals are required to form the grammar. Semantic actions and precedence rules are optional. The colon and the semicolon are required yacc punctuation. Semantic actions allow you to associate actions to be performed each time that a rule is recognized in the input process.
those $$ , $1 , $3 are the semantic values for for the symbols and tokens used in the rule in the order that they appear. The semantic value is that one that you get in yylval when the scanner gets a new token.
A yacc specification consists of a mandatory rules section, and optional sections for definitions and user subroutines. The declarations section for definitions, if present, must be the first section in the yacc program.
Yacc can not accept ambiguous grammars, nor can it accept grammars requiring two or more symbols of lookahead.
Yes it can. Yacc creates an LALR(1) parser -- the (1) means 1 token of lookahead -- so it may read ahead 1 token past the end of the tokens for a rule before reducing that rule. The existence of semantic actions is irrelevant, as the semantic action is just some C code to run just before reducing a rule.
Note that there's no guarantee that it will ALWAYS read ahead a token. The parser created by yacc or bison sometimes uses 'default reductions' -- states where it can reduce a rule WITHOUT having to read the next token first. This happens whenever the reduction of a rule is independent of the next token.
In this specific example, a default reduction could be used for the integer
rule, so it might reduce it without lookahead, but again there's no guarantee -- default reductions are an optimization used by some (but not all) implementations of yacc.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With