Re: Grammar ambiguity

"Jocelyn Coulmance" <>
12 Feb 2000 21:29:42 -0500

          From comp.compilers

Related articles
Grammar ambiguity (Joachim Durchholz) (2000-02-05)
Re: Grammar ambiguity (Ira D. Baxter) (2000-02-10)
Re: Grammar ambiguity (Robert Sherry) (2000-02-10)
Re: Grammar ambiguity (Jocelyn Coulmance) (2000-02-12)
Re: grammar ambiguity world! (Chris F Clark) (2000-02-12)
Re: Grammar ambiguity (Joachim Durchholz) (2000-02-12)
Re: grammar ambiguity (Chris F Clark) (2000-02-12)
Re: Grammar ambiguity (Charles E. Bortle, Jr.) (2000-02-13)
Re: Grammar ambiguity (Jocelyn Coulmance) (2000-02-19)
Re: grammar ambiguity (2000-02-21)
[7 later articles]
| List of all articles for this month |

From: "Jocelyn Coulmance" <>
Newsgroups: comp.compilers
Date: 12 Feb 2000 21:29:42 -0500
Organization: Guest of France-Teaser
References: 00-02-015
Keywords: parse

Joachim Durchholz <> a écrit

> Unfortunately, trying to rewrite a grammar for LALR is error-prone (at
> least for me) and time-consuming; we're currently talking about
> extending an existing language which is sort-of unambiguous (with a
> rule that states "a semicolon between statements is optional unless it
> is needed to disambiguate the program"). The language is easy to parse
> with an Earley algorithm but a nightmare with yacc; unfortunately,
> Accent or other Earley-based parsers will not tell me whether a CFG is
> ambiguous or not.

Maybe you should try to write a LALR(k) grammar rather than a LALR(1)
one. LALR(k) grammars allow much more natural constructs. In this
case VisualParse is a nice tool than can save you a lot of time.

As for the semicolon issue, - if you are talking about Eiffel, you can
insert an optional semicolon in the grammar and resolve the conflict
in favour of a shift. The parser will accept some illegal inputs but
later stages will correctly discard them. With this rule, Eiffel is
LARL(2) but for reasons unrelated to semicolons: the optional 'end' in
Feature_adaptation (see §6.3) and the optional Debug_keys in Debug
(the string '(' Manifest_string ')' is the start of a Compound if
followed by '.' , a Debug_keys otherwise).

- if you are talking about a new language, get rid of this rule ;) A
way to do so is to treat semicolons and line terminations as
equivalent and force one of them in certain places:

(a+b).p2 -- 2 different instructions since there is a line termination in

p1; (a+b).p2 -- idem since there is a semicolon

p1(a+b).p2 -- only one instruction

In your grammar simply add semicolons where needed and make your lexer
return a semicolon where it encounters a line termination. Then
discard any extraneous semicolon either by redefining the error
recovery procedure or by augmenting the grammar with optional
semicolons in each state.

If you need some help, I can help you on both points.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.