Re: Operator-precedence v.s. LL(1)

tfj@apusapus.demon.co.uk (Trevor Jenkins)
Sun, 29 Aug 1993 20:09:04 GMT

          From comp.compilers

Related articles
Opeartor-precedence v.s. LL(1) ejxue@ntu.ac.sg (1993-08-28)
Re: Operator-precedence v.s. LL(1) tfj@apusapus.demon.co.uk (1993-08-29)
Re: Operator-precedence v.s. LL(1) bart@majestix.cs.uoregon.edu (1993-08-30)
Re: Operator-precedence v.s. LL(1) spencer@cwis.unomaha.edu (1993-09-07)
Re: Operator-precedence v.s. LL(1) dww@cli.com (1993-09-07)
| List of all articles for this month |

Newsgroups: comp.compilers
From: tfj@apusapus.demon.co.uk (Trevor Jenkins)
Keywords: parse, LL(1)
Organization: Compilers Central
References: 93-08-111
Date: Sun, 29 Aug 1993 20:09:04 GMT

ejxue@ntu.ac.sg writes:


>Textbooks on compilers usually contain discussions about
>the relationships between the other types of grammars.


Very few textbooks distinguish between grammars and languages. After
reading many of the ``standard'' works one is left with the impression that
because a LALR(1)-based compiler generator is used then the ``language'' is
itself LALR(1). Though you can substitute your favourite parsing scheme for
LALR(1) as appropriate.


>I do not seem to come across a discussion regarding to
>the grammars accepted by operator-precedence and LL(1)
>(or recursive descent).


The dragon books (Green or Red) do not make this distinction. However, in
Tremblay and Sorenson there is a short$ comparison of parsing schemes. They
have a diagram which attempts to relate the various schemes together. I'll
try to reproduce their diagram here but you'd do better to refer to p410 of
``The Theory and Practice of Compiler Writing'' for better rendition.


                  Context-Free
                            |
                            +------------+
                            | |
              Unambiguous Operator
              Context-free Precedence
                            |
                        LR(k)
                            |
                            +------------------+
                            | |
                        LR(1) MSP
                            +-------+ |
                      LALR(1) | Extended Prec.
          +--------+ | |
          | SLR(1) +--------+ |
          | | | |
          | +---------------+| |
      LL(1) | Simple
                        LR(0) Precedence


>(1) What is the precise relationship between the two? (op prec and LL(1))


Hopefully their diagram puts them (and other schemes) into perspective.


--


Regards, Trevor.


---------------------------------------------------------------------------
Trevor Jenkins
134 Frankland Rd, Croxley Green, RICKMANSWORTH, WD3 3AU, England
email: tfj@apusapus.demon.co.uk phone: +44 (0)923 776436 radio: G6AJG


      "We need bigger and better books", Jimmy Tingle (Damned in the USA)


--


Post a followup to this message

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