Syntax, Grammar

 home  Bib Algorithms Bioinfo FP Logic MML Prog.Lang and the mmlist

Prog'Langs
glossary
Grammar
Arith'Exp'
Abstract-syn
Top-Down
Bottom-Up
A Context-Free Grammar G = <N, T, S, P> where
T is a finite set of terminal symbols,
N is a finite set of non-terminal symbols,
S is the start symbol, S:N,
P is a finite set of production rules of the form,
X ::= &alpha where X:N and α:(N+T)*
(X -> α is alternative notation)
rules with a common LHS, X ::= α, X ::= β, X ::= ... , are often shown thus:
X ::= α | β | ...
e.g., see the grammar of [arithmetic expressions].

Definitions   =>, =>*, =>+ :
α => β if β can be derived from α using a single production rule,
α =>* β if β can be derived from α using zero or more applications of production rules,
α =>+ β if β can be derived from α using one or more applications of production rules,
where α, β :(N+T)*

Definition:
γ is a sentential form if γ:(N+T)* and S =>* γ.

Definition:
γ is a sentence in the language defined by G if γ:T* and S =>+ γ.
(In some sources word is used in place of sentence.)

Definition:
The language L(G) = {γ:T* s.t. S =>+ γ},
that is, L(G) is the set of sentences that can be derived from S.

A derivation can be represented by a (derivation-) parse tree. (However, a parse tree is often based on simpler abstract syntax rather than concrete syntax.)

Definitions   lm=>, lm=>*, lm=>+,   rm=>, rm=>*, rm=>+ :
α lm=> β if β can be derived from α by applying a single production rule to the left-most non-terminal symbol within α.
&alpha lm=>* β if β can be derived from &alpha using zero or more left-most applications of production rules.
&alpha lm=>+ β if β can be derived from &alpha using one or more left-most applications of production rules.
(Similarly rm=>, rm=>*, rm=>+, and right-most.)

Definitions:
γ is a left sentential form if γ:(N+T)* and S lm=>* γ.
γ is a right sentential form if γ:(N+T)* and S rm=>* γ.

A [top-down] left-to-right parser performs left-most derivations.

A [bottom-up] left-to-right parser performs right-most derivations in reverse!

Sources

The dragon book, Ch.4.
Search for [parse] and/or [grammar] in the [Bib].
The [Algol-60 Revised Report],
which includes the first(?) formal definition of the syntax of a significant programming language.
window on the wide world:
 The Darwin Awards V: Next Evolution

 Linux  Ubuntu free op. sys. OpenOffice free office suite, ver 3.4+ The GIMP ~ free photoshop Firefox web browser FlashBlock like it says!

 © L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated), Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University, was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.) Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Tuesday, 18-Jun-2019 23:09:01 AEST.