Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compilers > #2910

Re:Some questions about recursive descent?

Show all headers | View raw

On 27 Feb 2022 16:37:05 EST, Johann 'Myrkraverk' Oskarsson
<johann@myrkraverk.com> asked in Newsgroup comp.compilers:

| I have some questions about the construction of
| recursive descent parsers.  The reason for my questions
| is that I know production compilers /use/ recursive
| descent. My first question is: how are production
| recursive descent parsers constructed?

If you want to see another example of this, since I added features to
it, is the XDPascal compiler, available from
https://github.com/electric-socket/xdpw or https://XDpascal.com. Now,
what I'm going to do is explain why and how this is done.

Pascal syntax requires that, after a procedure or function signature,
and any constants, types or variables are declared, it must have a
block. This is a BEGIN, zero or more statements, each separated by a
semicolon, then an optional semicolon, then END and a semicolon if it's
a procedure or function, a period if it's the end of a program. A syntax
diagram may help here:

Block:      ^______________>|
            |               V
--->BEGIN---+-->Statement---+-->V--------->^----> END --->
            ^_______ ; <____V   |__> ;_>__|

In the code example below, any identifier ending
in TOK is the token for that symbol or keyword,
e.g. DOTOK for DO, DOTTOK for period, etc.

So at the end of the compile, the compiler would
have a piece of code similar to this:

  block;
  nexttoken;
  if thistoken<>DOTTOK then error('Period expected');
  finishcompiling;

  Procedure "block" would have something similar to
  the following:

  repeat
       statement;
  until thistoken = ENDTOK or END_OF_FILE ;


Procedure "Statement" would look like this:

  nextToken;
   Case thisToken of
      Identifier : Identstmt;
      FORTOK: ForStmt
      REPEATTOK: RepeatStmt;
      BEGINTOK: Block;           // [1]
      ...
      WHILETOK: WhileStmt
    ELSE
       Error('Syntax error');


FOR statement:
   ----> FOR --> := --> ident ------> expression -->|
   |<-----------------------------------------------V
   V--V------- TO ----->----> expression --> DO --|
      V____> DOWNTO -->|                          |
                                                  |
   |<---------------------------------------------V
   V--------- statement ----------------->

Now, procedure ForStmt might be coded like this:

    nexttoken;
    if thistok <> BECOMESTOK then
      error(' := expected');
    nexttoken;
    if thistok <> identTok then
       error(' Identifier expected ');
    ...

and so on until:

    nexttoken;
    if thistok <> DOTOK then
      error(' DO expected');
    nexttoken;
    statement;

Now, if you look, at // [1], the case selector for
the token BEGIN calls procedure block again, while
it itself was called by block earlier. And, after the
DO token in FOR, statement calls itself.

If you notice, recursive descent works because each
statement in the program is processed until a "trigger"
token exits that state back to where it was called.
On return, syntax checking continues with the next
token after the one that caused a block or statement
procedure to be called.

I hope this example helps you to understand recursive
descent parsing.


XDPascal.com: The (new) home of the XDPascal Compiler.
----
"The lessons of history teach us - if they teach us anything - that no
one learns the lessons that history teaches us."
Paul Robinson <XDpascal@XDPascal.com> / <paul@paul-robinson.us>

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Some questions about recursive descent? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.com> - 2022-02-27 19:02 +0000
  Re: Some questions about recursive descent? gah4 <gah4@u.washington.edu> - 2022-02-27 17:13 -0800
  Re: Some questions about recursive descent? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-02-28 06:48 +0100
  Re: Some questions about recursive descent? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-02-28 07:43 +0000
    Re: Some questions about recursive descent? Alain Ketterlin <alain@universite-de-strasbourg.fr.invalid> - 2022-02-28 21:52 +0100
      Re: Some questions about recursive descent? Johann 'Myrkraverk' Oskarsson <johann@myrkraverk.invalid> - 2022-03-01 01:40 +0000
        Re: Some questions about recursive descent? anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2022-03-01 08:01 +0000
        Re: Some questions about recursive descent? Alain Ketterlin <alain@universite-de-strasbourg.fr> - 2022-03-01 23:13 +0100
        Re: Some questions about recursive descent? Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2022-03-02 05:52 +0100
    Re:Some questions about recursive descent? "Paul Robinson" <xdpascal@xdpascal.com> - 2022-03-05 14:46 -0600
  RE: Some questions about recursive descent Christopher F Clark <christopher.f.clark@compiler-resources.com> - 2022-02-28 15:40 +0200

csiph-web