上下无关文法
文法被用于组织编译器前端，文法自然地描述了大多数程序设计语言构造的层次化语法结构，例如java的if-else语句有如下的形式：
if(expression) statement else statement
用expr表示表达式，变量stmt表示语句，构造规则表示：
Stmt->if(expr)stmt else stmt（产生式）
->:可以具有如下形式
If ():终结符号
expr stmt :非终结符号
文法定义
- 终结符号集合（词法单元），终结符号是该文法所定义的语言的基本符号的集合
- 非终极符号集合（语法变量），每个非终结符号表示一个终结符号串的集合。
- 产生式集合，其中每个产生式包括一个称为产生式头或左部的非终极符号，一个箭头，一个称为产生式体或右部的由终结符号及非终结符号组成的序列。产生式主要用来表示某个构造的某种书写形式，如果产生式头非终极符号代表一个构造，那么该产生式体就代表了该构造的一种书写方式。
- 指定一个非终极符号为开始符号。
词法单元和终结符号
在编译器中，词法分析器读入源程序的字符序列，将它们组织为具有词法含义的词素，生成并输出代表这些词素的词法单元序列。词法单元由两个部分组成：名字和属性值。
描述文法的时候。列出该文法的产生式，并且首先列出开始符号对应的产生式。假设数位，符号（<,<=）和黑体字符串（while）都是终结符号。斜体字符串表示非终结符号，所有非斜体的名字或者符号都可以看做终结符号，为表示方便，以同一个非终结符号为头部的多个产生式的体可以放在一起表示，不同体之间用“|（或）”分隔。
推导
根据文法推导符号串时，首先从开始符号出发，不断将某个非终极符号替换为该非终结符号的某个产生式的体。可以从开始符号推导得到的所有终结符号串的集合称为该文法定义的语言。
二义性
一个文法可能有多棵语法分析树能够生成同一个给定的终结符号串。
练习
Consider the context-free grammar:
S -> S S + | S S * | a
1. Show how the string aa+a* can be generated by this grammar.
2. Construct a parse tree for this string.
3. What language does this grammar generate? Justify your answer.
Answer
1. S -> S S * -> S S + S * -> a S + S * -> a a + S * -> a a + a *
3. L = {Postfix expression consisting of digits, plus and multiple signs}
What language is generated by the following grammars? In each case justify your answer.
1. S -> 0 S 1 | 0 1
2. S -> + S S | - S S | a
3. S -> S ( S ) S | ε
4. S -> a S b S | b S a S | ε
5. S -> a | S + S | S S | S * | ( S )
Answer
1. L = {0n1n | n>=1}
context-free grammars
A grammar is a set of rules for putting strings together and so corresponds to a language.
grammars
A grammar consists of:
- a set of variables(also called nonterminals),one of which is designated the start variable;It’s customary to use upper-case letters for variables;
- a set of terminals(from the alphabet);
- a list of productions(also called rules)
Using a Grammar
A production allows one to take a string containing a variable and replace the variable by the RHS of the production.
String w of terminals is generated by the grammar if, starting with the start variable, one can apply productions and end up with w, The sequence of strings so obtained is a derivation of w.
We focus on a special version of grammars called a context-free grammar (CFG), A language is context-free if it’s generated by a CFG.