14 Mar 2003 11:31:24 -0500

Related articles |
---|

Terminals, non-terminal, syntax, semantics: some really naive questi rmyers1400@attbi.com (Robert Myers) (2003-03-09) |

Re: Terminals, non-terminal, syntax, semantics: some really naive cfc@world.std.com (Chris F Clark) (2003-03-14) |

Re: Terminals, non-terminal, syntax, semantics: some really naive arnold@skeeve.com (2003-03-14) |

Re: Terminals, non-terminal, syntax, semantics: some really naive slk14@earthlink.net (SLK Parsers) (2003-03-14) |

Re: Terminals, non-terminal, syntax, semantics: some really naive branco@canal13.com.br (2003-03-17) |

From: | "SLK Parsers" <slk14@earthlink.net> |

Newsgroups: | comp.compilers |

Date: | 14 Mar 2003 11:31:24 -0500 |

Organization: | Parsers Inc. |

References: | 03-03-039 |

Keywords: | parse |

Posted-Date: | 14 Mar 2003 11:31:24 EST |

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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.