How to clear conflicts in OCamlYacc or Menhir

Asked 1 years ago, Updated 1 years ago, 86 views

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

2022-09-30 16:01

1 Answers

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

  • Write down the rule until the generator does not get lost in conflict because the rule is often too rough.
  • Reduce the number of applicable rules by specifying token priority and direction of merge
  • Reduce/reduce should be resolved
  • If shift/reduce, shift priority is given, so if you're satisfied with it, leave it alone (but your YACC experience won't go up)

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.

Using Menhir

In OCaml, OCamlYacc is old and uses Menhir, which is no longer used.
Also, use menhir--explain to understand where the conflict is.

How to Read Menhir Reports

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.


2022-09-30 16:01

If you have any answers or tips


© 2024 OneMinuteCode. All rights reserved.