Re: Grammar ambiguity

Joachim Durchholz <joachim.durchholz@halstenbach.com.or.de> 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:


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


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.


Regards
Jocelyn

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