Re: Parsing fully context-free grammars

"Evangelos Drikos" <drikosv@otenet.gr>
7 Oct 2005 21:48:29 -0400

          From comp.compilers

Related articles
[3 earlier articles]
Re: Parsing fully context-free grammars haberg@math.su.se (2005-09-23)
Re: Parsing fully context-free grammars paul@parsetec.com (Paul Mann) (2005-10-02)
Re: Parsing fully context-free grammars haberg@math.su.se (2005-10-02)
Re: Parsing fully context-free grammars drikosv@otenet.gr (Evangelos Drikos) (2005-10-03)
Re: Parsing fully context-free grammars paul@parsetec.com (Paul Mann) (2005-10-04)
Re: Parsing fully context-free grammars hannah@schlund.de (2005-10-06)
Re: Parsing fully context-free grammars drikosv@otenet.gr (Evangelos Drikos) (2005-10-07)
Re: Parsing fully context-free grammars lowell@coasttocoastresearch.com (lowell@coasttocoastresearch.com) (2005-10-20)
| List of all articles for this month |

From: "Evangelos Drikos" <drikosv@otenet.gr>
Newsgroups: comp.compilers
Date: 7 Oct 2005 21:48:29 -0400
Organization: An OTEnet S.A. customer
References: 05-10-037 05-10-047
Keywords: parse

Hi all,


Paul questioned that the restated grammar is acceptable by LR parsers and
Hannah explained:


>> <other-stmt> ::= ... define other statements ...






I'll try a second one, this time more accurate.






Let us say that the <other-stmt> can be a <while-stmt> or a <compound-stmt>
or an <assignment>. I provide an example BNF grammar in full detail, given
at the end of this message.






I took me a while to try some texts with an SLR, a LALR(1), a CLR(1), and a
modified/hybrid GLR (Lex Analyzer "enhanced" by LR(0) ) but it works. In all
tests, the parsers accept the same input, and interpret the same as with the
grammar having the dangling else ambiguity when the shift action is favored
in a shift/reduce conflict. With the dangling else ambiguity the modified
GLR accepts also the same input but there are multiple interpretations; with
the restated grammar there aren't.






Maybe I haven't tested yet the "text" that will allow me to see the problem.






Any suggestions are welcome.






Thanks in advance,


Ev. Drikos.




(Below: The example Grammar without else ambiguity + Lexical Conventions)






-------------------------------------------


THE GRAMMAR


------------------------------------------






<grm> ::=
                      <stmts>






<stmts> ::=
                      <stmts> <stmt>
          | <stmt>




<stmt> ::=
                      <while-stmt>
          | <if-stmt>
          | <if-else-stmt>
          | <compound-stmt>
          | <assignment>




<while-stmt> ::=
                      while ( cond ) <stmt>




cond ::=
                      <id> <op> <id>




<op> ::=
                      <equal>
          | <not-equal>
          | <ge>
          | <gt>
          | <le>
          | <lt>




<if-stmt> ::=
                      if ( cond ) <stmt>




<if-else-stmt> ::=
                      if ( cond ) <non-if-stmt> else <stmt>


<non-if-stmt> ::=
                      while ( cond ) <non-if-stmt>
          | if ( cond ) <non-if-stmt> else <non-if-stmt>
          | <compound-stmt>
          | <assignment>




<compound-stmt> ::=
                      <lbrace> <stmts> <rbrace>
          | <lbrace> <rbrace>




<assignment> ::=
                      <id> = <id>




-----------------------------------------------


THE LEXICAL CONVENTIONS (the <whitespace> should be ignored by or not
returned to the parser)


-----------------------------------------------






Token ::=
                      while
          | (
          | )
          | <lbrace>
          | <rbrace>
          | if
          | else
          | <whitespace>
          | <equal>
          | <not-equal>
          | <ge>
          | <gt>
          | <le>
          | <lt>
          | <id>
          | ;
          | =




while ::=
                      w h i l e




<lbrace> ::=


                      {


<rbrace> ::=
                      }


if ::=
                      i f


else ::=
                      e l s e


<whitespace> ::=
                      <space> ...


<space> ::=
                      \s
          | \t
          | \n
          | \r
          | \r \n
          | \n \r


<equal> ::=
                      = =


<not-equal> ::=
                      ! =


<ge> ::=
                      > =


<gt> ::=
                      >


<le> ::=
                      < =


<lt> ::=
                      <


<id> ::=
                      <letter> ...


<letter> ::=
                      a
          | b
          | c
          | d
          | e
          | f
          | g
          | h
          | i
          | j
          | k
          | l
          | m
          | n
          | o
          | p
          | q
          | r
          | s
          | t
          | u
          | v
          | w
          | x
          | y
          | z


Post a followup to this message

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