Re: Verified compilers?

["Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>]

On Wed, 07 Mar 2012 06:33:54 +0100, Yannick Duch�ne (Hibou57) wrote:

> Le Tue, 06 Mar 2012 18:43:21 +0100, Dmitry A. Kazakov  
> <mailbox@dmitry-kazakov.de> a �crit:
> 
>> On Tue, 6 Mar 2012 09:24:04 -0800 (PST), Shark8 wrote:
>>
>>> I seem to recall someone on this forum doing a table-driven approach,
>>
>> I do:
>>
>> http://www.dmitry-kazakov.de/ada/components.htm#Parsers_etc
> I did not investigate, so the question may be stupid: why two separate  
> stacks?

Because you need to store arguments some of which appear before the
operators that bound them. That is the argument's stack. The operations too
may be reordered according to the association priorities. That is the
operation's stack.

Consider parsing: A + B * C + D

A+B*C+D --->
   AS: A
   OS: 
+B*C+D --->
   AS: A
   OS: +
B*C+D  --->
   AS: A; B
   OS: +
*C+D  --->
   AS: A; B
   OS: +; *
C+D --->
   AS: A; B; C
   OS: +; *
+D --->  pop *
   AS: A; B*C
   OS: +
+D --->  pop +
   AS: A+(B*C)
   OS: +
D --->
   AS: A+(B*C); D
   OS: +
---> pop +
   AS: (A+(B*C))+D
   OS:

> I did a basic expression parser too some long time ago, and it had  
> a single stack.

Well, Turing machine has only one tape, so yes you could do that. The
question is why.

P.S. This method has nothing to do with being table-driven. Table-driven is
the lexer, which recognizes operators using tables. So the engine is same
for all expressions.

Tables are also used for the recursive descent parser put around infix
expression parser. At each level there is a table of expected keywords. The
input is matched against the table and parser does something. Some leaves
are expressions, for them the described above method is used.

Infix expression is only really difficult part here. The rest is just
trivial for almost any normal language.

I was always wondering why people bother to study grammars, LR, LL parsers
and other useless stuff. This is a great example of making a "science" out
of nothing and for nothing.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de