Re: Parsing fully context-free grammars

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

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