Re: A question about a LL parser

On 27 Apr., 02:45, Chad <cdal...@xxxxxxxxx> wrote:
The question comes from the following URL

http://en.wikipedia.org/wiki/LL_parser

They parse ( 1 + 1 ), using the following grammar rules.

1. S → F
2. S → ( S + F )
3. F → 1

On the first '(' from the input stream and from the 'S' stack, they
apply rule 2. How do they know it's rule 2 and say not rule 1?

I would say: Because rule 2 starts with an '('.
If you want to understand parsing look at how a Pascal
compiler parses a program. Pascal can be parsed with LL(1).
There is something like the current symbol (which is not the
same as a character). A symbol can be an identifier, a literal
one of the reserved words, an operator, a paren, ... Symbols
are read by the scanner (which also has the job of skipping
comments, and processing pragmas).

The parser does all decisions based on the current symbol.
When necessary the parser calls the scanner to get the next
symbol. Pascal uses a recursive descend parser which maps
very closely to the syntax of Pascal.

For example:
The procedure to parse statements looks at the current
symbol and when it is the reserved symbol 'if' it calls the
procedure 'ifstatement'. If a statement does not start with a
reserved word it can be a procedure call or an assignment...

The source of the P4 Pascal compiler can be found here:
http://homepages.cwi.nl/~steven/pascal/

Hope that helps.

Greetings Thomas Mertes

Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.
.

Relevant Pages

  • Re: Some clarification on "Pre-Parsers" and other bits
    ... the "C" you are talking about is a language. ... would be confusing) that is a parser for the C language. ... A typical compiler ... the input is syntactically correct. ...
    (alt.lang.asm)
  • Re: Compile time of C++ vs C#
    ... invoking my experience as a compiler writer, I can give a fairly solid ... entire assembly at once, and the parser manages to work, initially, with an ... judging from MSVC's ASM output on x64, well, their optimizer is not exactly ... movss, xmm0 ...
    (comp.compilers)
  • Re: Generating a simple hand-coded like recursive descent parser
    ... compiler is for an existing BASIC language. ... hand-coded recursive descent parser? ... I see no reason to use that to bootstrap a compiler. ... There's no specific algorith to build the AST. ...
    (comp.compilers)
  • Re: Has anyone hand-written a scanner/parser module?
    ... tools to create scanner/parser modules for their compiler projects. ... was wondering if anyone has developed a scanner or parser that they ... personally hand-wrote? ...
    (comp.compilers)
  • Re: string parsing algorithm
    ... Most compilers etc must have a string parser like this, ... tools called compiler compilers. ... First step is lexing and parsing ... Lexing converts an incoming stream of characters into a stream of "tokens" ...
    (comp.programming)