Syntax, Grammar

LA home
Computing
 Algorithms
 Bioinformatics
 FP,  λ
 Logic,  π
 MML
 Prog.Langs

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:

Computer Science Education Week

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 Monday, 29-Dec-2014 08:32:32 EST.