context-free grammar (CFG)
上下文无关文法
相关概念
- 大多数编译器和解释器都包含一个语法分析器 (parser)，用来获取程序设计语言的文法。
- 一个文法有一组替换规则 (substitution rule，又称为产生式 production)
- 每条规则由符号和字符串构成。
- 符号包括变元 (variable) 和终结符 (terminal) 。
- 变元常用大写字母表示，终结符常用小写字母、数字或特殊符号表示。
- 根据文法生成描述其语言的每一个字符串获取一个字符串的替换序列称为派生 (derivation)
- 写下起始变元；
- 取一个已写下的变元，找到该变元开始的规则，把它替换成规则右边的字符串；
- 重复上一个步骤，直到写下的字符串没有变元为止。
推导方法
S → AB
A → a|t
B → +CD
C → a
D → a
最左推导
Left-most Derivation: At each step, replace the left most non terminal
S → AB → aB → a+CD → a+aD → a+aa
最右推导
Right-most Derivation
S → AB → A+CD → A+Ca → A+aa → a+aa
形式化定义
上下文无关文法是一个4元组
- ：有穷变元集（variables）
- ：与不相交的有穷终结符集（terminals）
- ：有穷规则集（rules）（每条规则由一个变元和一个由变元及终结符组成，形如）
- ：起始变元
- 一步派生：
- 任意步派生： 或
文法的歧义性
Ambiguity，或者称为二义性
如果文法以不同的方式产生同一个字符串，则称文法歧义地产生这个字符串。
例1
这个文法歧义地产生字符串
例2
CS310 Lecture5- Grammar:
- String:
String 是怎么根据既定语法推导出来的？
This string has two parse trees.
Dealing with Ambiguity: Most direct method is to rewrite grammar unambiguously
Enforces precedence of * over +
乔姆斯基范式
Chomsky normal form, CNF
- When working with context-free grammars, it is convenient to have them in simplified form.
- A context-free grammar is in Chomsky normal form if every rule is of the form
a 是任意的终结符，A、B 和 C 是任意的变元，且 B 和 C 不能是起始变元。此外，允许规则 ， 其中 S 是起始变元。
- 例：把原先的CFG（左边）转换成乔姆斯基范式（右边）
下推自动机
Pushdown automata, PDA
相关概念
- 下推自动机类似于有穷自动机，但是它有一个称为栈 (stack) 的额外设备。
- 栈“先进后出” ，在控制器的有限存储量之外提供了附加的存储，使得下推自动机能够识别某些非正则语言。
- 它与上下无关文法有等价性
- 一个语言是上下文无关的， 当且仅当存在一台下推自动机识别它。
- The class of CFLs is closed under ∪,∘,∗.
- The class of CFLs is not closed under ∩.
- If 𝐴𝐴 and 𝐵𝐵 are CFLs then 𝐴𝐴∩𝐵𝐵 may not be a CFL.
形式化定义
下推自动机是一个6元组
例：
- 每读一个0，把一个0推入栈，每读一个1，把一个0弹出栈
- 如果当读完输入串时，恰好排空栈中的0，则接受，否则拒绝
- 如果在还有1没有读完时，栈就排空，则拒绝
- 如果在1读完时，栈中还有0，则拒绝
- 如果0出现在1的后面，则拒绝
泵引理
如果 是上下文无关语言 ，则存在数 ， 使得 中任何一个长度不小于 的宇符串 都能被划分成 5 段 ，且满足下述条件：
- 对于每一个
例子
构造上下文无关
The alphabet Σ is {0,1}
The empty set
空字符串不能等同于空集合 ❌
{w | w contains at least three 1s}
❌
无法确定1的位置，任意空格插入即可
类似递归， 前后都需出现
记得多次循环
{w | w starts and ends with the same symbol}
{w | the length of w is odd}
或
不能带上空串，否则会变奇数
{w | the length of w is odd and its middle symbol is a 0}
要放在中间，不能放左或右，
否则无法保证中间是0
{w | w is a palindrome}
可以合并 🧐?
证明上下文无关
即能够构造出相关文法
Show that C= {x#y| x, y {0,1}* and x y} is a context-free language.
Define the CFG for C is as follows:
🧐 这么写可以吗？
As the grammar for C is defined in terms of CFG. The language produces a string that contains x#y , and x and y are different character for same indexposition. Hence, it is proved that C is Context Free Language.
Show that E = { | i ≠ j and 2i ≠ j} is a context-free language.
- .
Therefore, the language is context free language.
证明非上下文无关
分析时注意横跨的情况比较多，不要遗漏
Show that the following languages are not context free
如果像判断非正则时，取 ❌
那么按如下划分时它就能够被抽取
横跨 ，且 都在 0 里面，那么循环后 0 的个数还是有可能相等
✔️
为了满足，则只有两种分割方式：
- 全部是0
does not satisfy the 1:2:3 length ratio of 0
- 混有一个#
contains more than two #s