I use OCamlYacc and Menhir, but when conflicts occur, I somehow erase them because of a try-and-error.
If you know how to use the tool or how to use it, please let me know.
ocaml
Resolving YACC's shift/reduce, reduction/reduce conflict is often written in parser's textbook or online information.First of all, understand the basic operating principles of YACC in its own way.For example, http://guppy.eng.kagawa-u.ac.jp/2006/ProgLang/bison-1.2.8/bison-ja_8.html.
It's in every textbook, but it's generally
That will solve the problem.Read the conflict report for each parser generator to see where to fix it.I think this is the only one.
I don't know much about general parsers, so I'll just introduce you to specific OCaml information.
In OCaml, OCamlYacc is old and uses Menhir, which is no longer used.
Also, use menhir--explain
to understand where the conflict is.
Use the following example to read <basename>.conflicts
: This is a little bit more than the reduction/reduce example from documents such as Bison:
%token WORD
%token START
%start<int>statement
%%
statement:
| START sequence {$2}
;
sequence:
| /*empty*/{0}
| maybeword {$1}
| sequence WORD {$1+$2}
;
maybeword:
| /*empty*/{0}
| WORD {1}
;
%%
The code above is menhir --explain x.mly
to create the following x.conflicts
files, which consist of a collection of conflict descriptions beginning with the line **Conflicts(...)instate XXX.
.While reading the report, it's easy to read if you see a **Conflict(...)
and you move on to another conflict description:
**Conflict(shift/reduce/reduce)instate1.
** Tokens involved:WORD#
** The following plans concentrate on token WORD.
** This state is reached from statement after reading:
START
There is a conflict around the processing for WORD.This occurs after reading START
for the first time from statement
.It seems that shift/reduce and reduce/reduce are occurring at the same time.
**The derivations that appear below have the following common factor:
** (The question mark symbol(?) presents the spot where the derivations begin to different.)
statement
START sequence
(?)
The multiple interpretations that cause conflict are common to the point where statement
is START sequence
, but beyond that, what should we do with sequence
?Below is an explanation of how each is interpreted.
**Instate1, looking ahead at WORD, reducing production
** maybeword->
** is permitted cause of the following sub-delivery:
sequence WORD//lookahead tokenappears
maybeword//lookahead token is inherit
.
If you have a read-ahead token WORD
, you can redo this WORD
and get a sequence
—Read from below to get a configuration called ->maybword->sequence
.(If you consume the WORD
of the read-ahead token, it will be sequence WORD->sequence
)..
is marked here where the parser is looking.
**Instate1, looking ahead at WORD, shifting is permitted
** cause of the following sub-delivery:
maybeword
. WORD
If you have a read-ahead token WORD
, you can use the shift to configure WORD->maybeword->sequence
from the bottom..WORD
is where the parser is now, and the read-ahead is WORD
.
**Instate1, looking ahead at WORD, reducing production
** sequence->
** is permitted cause of the following sub-delivery:
sequence WORD//lookahead tokenappears
.
You can configure sequence
without consuming this WORD
when you have a read-ahead token: ->sequence
(along with the read-ahead token WORD
to configure sequence WORD->sequence
.
Now, to eliminate conflict, just keep the acceptable set (assuming it's correct) and
This narrows the selectability of multiple rules by changing or prioritizing the rules,
But isn't there a mechanical way to do this anyway?
(If so, the parser generator should solve it on its own.)
I think it's best to read the conflict report carefully and understand the reason.
If you have any tips, I would like to know.
© 2024 OneMinuteCode. All rights reserved.