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

> I keep running across a small set of terms that, evidently
> everyone knows except me.


A context-free grammar consists of a set of nonterminals, a set of
terminals, a set of productions, and a single start symbol from the set of
nonterminals. The nonterminals in a grammar can be thought of as variables.
This is because during the course of parsing a grammar, the nonterminals are
subject to change. The terminal symbols can be thought of as being the
constants in a context-free grammar. The terminal symbols cannot be changed
because they constitute the vocabulary of the language that is derived from
the grammar. This language consists of all strings of terminal symbols that
can be formed using the rules of the grammar. The language of a grammar G is
referred to as L(G). A definition of a context-free grammar follows.


        Definition: A context-free grammar G is described as


                G = ( N, T, P, S )


                where


                        N is a finite set of nonterminal symbols.
                        T is a finite set of terminal symbols, disjoint from N.
                        P is a finite set of productions of the form


                                A --> alpha


                                where


                                        A in N
                                        alpha in ( N union T )*


                        S is a unique start symbol from N.


The set of productions constitutes the rules of the grammar. These are
sometimes referred to as rewriting rules because they specify how a
nonterminal can be rewritten, or expanded into a string of symbols from the
set


                                                ( N union T )*


Consider the following grammar:


                                                A --> B c D Grammar 2.1
                                                B -->
                                                D --> d


The first production in grammar 2.1 describes a way of rewriting nonterminal
A. The rule says that nonterminal A can be rewritten in the form "BcD".
Several conventions are implied in this grammar. The capital letters are
taken to be nonterminal symbols, and the lowercase letters represent
terminal symbols in the grammar. By convention, the left hand side
nonterminal of the first production in the grammar is assumed to be the
start symbol of the grammar. These conventions are useful because they make
it possible to completely specify a grammar simply by listing its
productions. The following can be inferred from the listing of grammar 2.1
above:


                                                N = { A, B, D }
                                                T = { c, d }
                                                S = A


----------------------------------------------------------------------------
This is an excerpt from the "Deterministic Parsing" chapter of "Parsers:
Theory and Implementation" on parsers.org.


http://parsers.org

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