Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
409 views
in Technique[技术] by (71.8m points)

compiler construction - Where is the shift/reduce conflict in this yacc grammar?

I'm writing a parser for a language called C-. I have to write the grammar so its not ambiguous and I can't use any %prec statements in Bison. I've corrected all but 1 shift/reduce conflict and I can't figure out where it is. Any ideas? My .output file gives the following info for where its occurring:

State 163

   44 matched: IF '(' simpleExp ')' matched . ELSE matched
   46 unmatched: IF '(' simpleExp ')' matched .
   48          | IF '(' simpleExp ')' matched . ELSE unmatched

    ELSE  shift, and go to state 169

    ELSE      [reduce using rule 46 (unmatched)]
    $default  reduce using rule 46 (unmatched)

The grammar:

stmt                : selectStmt
                    ;

expStmt             : exp ';'
                    | ';'

compoundStmt        : '{' localDecls stmtList '}'
                    ;  

stmtList            : stmtList stmt
                    |
                    ;

otherStmt           : compoundStmt
                    | expStmt
                    | iterStmt
                    | returnStmt
                    | breakStmt
                    ;     

localDecls          : localDecls scopedVarDecl
                    |
                    ;

selectStmt          : matched
                    | unmatched
                    ;
                
matched             : IF '(' simpleExp ')' matched ELSE matched
                    | otherStmt
                    ;

unmatched           : IF '(' simpleExp ')' matched
                    | IF '(' simpleExp ')' unmatched
                    | IF '(' simpleExp ')' matched ELSE unmatched
                    ;
                    
iterStmt            : WHILE simpleExp DO selectStmt
                    | FOR ID '=' iterRange DO selectStmt
                    ;

iterRange           : simpleExp
                    | simpleExp TO simpleExp
                    | simpleExp TO simpleExp BY simpleExp
                    ;

returnStmt          : RETURN ';'
                    | RETURN exp ';'
                    ;

breakStmt           : BREAK ';'
                    ;
question from:https://stackoverflow.com/questions/66053364/where-is-the-shift-reduce-conflict-in-this-yacc-grammar

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

The problem is that it is not only if statements which can be "matched". An iteration statement which ends with an unmatched statement is just as unmatched as an if statement which ends with an unmatched statement. That's what "matched" means.

So you have to divide your iterative statements into matched and unmatched variants. (This is why most people use precedence or expect declarations to deal with dangling else.)

Here's a simple example in case it becomes useful in the future. (Many of the non-terminals haven't been changed, so their definitions have been omitted. I also expanded a lot of abbreviations.)

statement: matched
         | unmatched
/* Statements which could have been extended with an else clause,
 * but haven't been. An unmatched statement can be the body of an
 * unmatched compound statement, which includes an `if` statement
 * whose `else` clause is unmatched. Unmatched also includes `if`
 * statements without an `else` clause.
 */
unmatched: "if" '(' simpleExp ')' statement
         | "if" '(' simpleExp ')' matched "else" unmatched
         | "while" '(' simpleExp ')' "do" unmatched
         | "for" IDENT '=' iterRange "do" unmatched
/* Statements which cannot be extended with an else clause.
 * In other words, in a `matched` every `else` matches some `if`.
 * Only `matched` statements can come between `if` and `else`, because
 * an unmatched statement would grab the `else` for itself.
 */
matched  : "if" '(' simpleExp ')' matched "else" matched
         | "while" '(' simpleExp ')' "do" matched
         | "for" IDENT '=' iterRange "do" matched
         | expStatement
         | returnStatement
         | breakStatement
         | '{' localDeclarations statementList '}'

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...