Re: Terminals, non-terminal, syntax, semantics: some really naive questions

Robert Myers wrote


> I find myself in the position of needing to know more about compilers
> than I thought I would ever want to know.


<snip>


> One Michael Peterson was brave enough to post [Q] Basic Terminology
> Questions 2001-01-05 11:10:09 PST


<snip>


> >For example, in the JavaCC distribution there is a very simple grammar
> >called Simple1. In the description of this grammar (and the others, also),
> >the words "terminals" and "non-terminals" are used to name what, to my naive
> >eye, look like, well, simple rules.
>
> This brave question eventually elicited a knowledgeable and thoughtful
> response from one Robert Rayhawk, whose response leaves me feeling
> that my queasy feelings are entirely justified.
>
> >The sense of the word 'terminal' in compiler discussions, is that the
> >thing is at the 'end'.
>
> Pretty easy to see that the terminals always wind up as the terminal
> leaf on a tree...at least the way the trees are usually drawn. Redraw
> the tree without rearranging the structure and the "terminals" could
> just as well wind up at the top.
>


<snip>


> Help!


:-))


Maybe it helps to know that parsing theory uses the terms introduced
by Linguistics; Linguistics' objective is to determine if a given set
of rules (a grammar) is capable of *generating* expressions of a given
"language". Notice that this is exactly the opposite objective of
parsing, which is to determine if a given input fits a language's
grammar.


So, in Linguistics, you'd start with an initial grammar rule and it
would generate (or produce) some result (therefore, the result of the
rule execution is named its "production"). This production would be
composed of a mix of an arbitrary number of a) reference(s) to other
rules, which should be executed; and b) final elements of the
language, which woudn't need further processing, heading straight to
output.


As a Linguist, you'd know that the grammar effectively describes a
given language if the execution of its rules lends to a situation
where the last executed rule's production needs no further processing,
that is, is formed only by the final elements of the language, without
references to other rules.


Well, as you may have guessed by now, these "final elements of the
language" are the so called "terminals"; since references to other
rules mean that further processing is needed (they never show up on,
say, the output), they're obviously called "non-terminals".


From this, you can see that we compiler designers and other adepts of
parsing theories are using the terms in reverse... :-)))


HTH.


Regards,


Branco.

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