Re: Parsing stack-based languages

anton@mips.complang.tuwien.ac.at (Anton Ertl)
29 Oct 1997 23:09:08 -0500

          From comp.compilers

Related articles
Postscript Parser withers@cs.man.ac.uk (1997-10-17)
Re: Postscript Parser quite@dial.pipex.com (1997-10-19)
Parsing stack-based languages nnylfv@ny.ubs.com (Olivier Lefevre) (1997-10-26)
Re: Parsing stack-based languages anton@mips.complang.tuwien.ac.at (1997-10-29)
| List of all articles for this month |

From: anton@mips.complang.tuwien.ac.at (Anton Ertl)
Newsgroups: comp.compilers
Date: 29 Oct 1997 23:09:08 -0500
Organization: TU Wien, Institut fuer Computersprachen
References: 97-10-091 97-10-096 97-10-120
Keywords: parse, interpreter, bibliography

Olivier Lefevre <nnylfv@ny.ubs.com> writes:
> What, then, is the theory (if any) underlying
> the parsers of such languages (Forth being another)?


In Forth every sequence of non-white-space characters is a word. Words
are separated by white space. I don't think this is complicated enough
to merit theoretical treatment, but in any case, it's a regular
(Chomsky type 3) grammar.


Some words do their own parsing when they are executed (typically
searching for a delimiter, in many cases white space). I am not aware
of a theory for that. But since we know how to implement it, there's
not that much need of a theory.


For Postscript the situation is similar, except that you would need a
context-free grammar (because a string can contain nested parentheses
pairs).


If you want some theory to describe well-formed (in some sense)
program fragments for stack-based languages, read [poeial94]; however,
this would probably run under "static semantics" in compiler
textbooks.


@InProceedings{poeial94,
    author = "Jaanus P{\"o}ial",
    title = "Forth and Formal Language Theory",
    crossref = "euroforth94",
    pages = "47--52"
}


@Proceedings{euroforth94,
    title = "EuroForth~'94 Conference Proceedings",
    booktitle = "EuroForth~'94 Conference Proceedings",
    year = "1994",
    key = "EuroForth '94",
    address = "Winchester, UK",
}


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html
--


Post a followup to this message

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