Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is the order of reduction defined in Yacc?

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?

like image 816
Alex Gaynor Avatar asked Sep 08 '12 13:09

Alex Gaynor


People also ask

What are the rules for yacc?

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.

What is $$ in yacc?

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.

What are the sections contain yacc specification?

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.

What yacc Cannot parse?

Yacc can not accept ambiguous grammars, nor can it accept grammars requiring two or more symbols of lookahead.


1 Answers

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.

like image 173
Chris Dodd Avatar answered Oct 17 '22 07:10

Chris Dodd