Re: Parsing stack-based languages

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
--

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