汪道之

有人的地方就有江湖

0%

编译原理第四章前导

发表于 更新于 分类于

形式语言与自动机

基础知识

字母表有非空性、有穷性、单一性

Σ代表字母表
ε代表空串
{ε}代表仅含有空串的集合
Φ代表空集
αβ代表两个字符串α与β的连接（并置）
α^n^ 代表α的n次连接，其中α^0^ =ε，α^n^ =α^n-1^ α 其中n>0
AB代表集合A与B的连接，A={a1,a2,a3,…,an}，B={b1,b2,b3,…,bm}

则AB=
{ a1b1，a1b2，a1b3，…，a1bm，
a2b1，a2b2，a2b3，…，a2bm，
a3b1，a3b2，a3b3，…，a3bm，
…
anb1，anb2，anb3，…，anbm }

注意：AФ=ФA=Ф，A{ε}={ε}A=A

A^n^ 代表集合A的n次连接（n次幂），A^0^ = {ε}，A^n^ = A^n-1^A n ≥ 1
A^^ 代表A上所有字符串的集合，称作集合A的克林闭包
A^^ = A^0^ ∪ A^1^ ∪ A^2^ ∪ …∪ A^n^
A^+^ 称为A的正闭包
A^+^=A^1^∪A^2^∪A^3^∪…∪A^n^

定义：

给定字母表∑，则∑*的任意子集L称为字母表∑上的一个语言。

设∑是一个字母表，∀L ⊆ ∑*, ∀x ∈ L, x称为L的一个句子。

eg：Σ＝{0，1}，请给出语言的形式表示

  1. 所有以0开头，以1结尾的串的语言。
  2. 所有以11开头，11结尾的串的语言。
  3. 所有长度为偶数的串的语言。
  4. 所有长度为奇数的串的语言。
  5. 所有包含子串01011的串的语言。
  6. 所有的第10个字符是0的串的语言。

answer：

  1. {0} {0,1}^*^ {1}
  2. {11} {0,1}^*^ {11} ∪ {11,111}
  3. {00,01,10,11}^*^
  4. {00,01,10,11}^*^ {0,1}
  5. {0,1}^^ {011011} {0,1}^^
  6. {0,1}^9^ {0} {0,1}^*^

形式语言与自动机理论简介

初步认识

语言的定义可以从两个方面进行：

  1. 从产生语言的角度
  2. 从接收（识别）语言的角度

  • 产生语言

    根据语言中的基本句子和其他句子的形成规则，得到（产生）该语言所包含的所有句子

    属于形式语言所研究的问题

  • 接收语言

    使用自动机模型来接收字符串，接收的所有字符串，也形成一个语言

    属于自动机所研究的问题

统一的理论

形式语言与自动机作为统一的理论，实际上包括3个方面的内容：

  1. 形式语言理论（产生语言）
  2. 自动机理论（接收语言）
  3. 形式语言与自动机的等价性理论
括号匹配串的语言

自然语言描述：

  1. （）是该语言的最基本的句子

  2. 若S是句子，则（S）是句子

  3. 若S是句子，则SS是句子

根据以上形成规则，我们可以：

  1. 产生该语言的任意的句子
  2. 判断某个串是否是该语言的句子——语法分析

巴克斯-诺尔范式（BNF）描述：

  1. <括号匹配串>::=()

  2. <括号匹配串>::=(<括号匹配串>)

  3. <括号匹配串>::=<括号匹配串><括号匹配串>

Chomsky描述：

  1. S->()

  2. S->(S)

  3. S->SS

注：为方便起见，箭头打成->

术语：

  1. S称为非终结符，是在推导中可以被替代的符号。
  2. （）称为终结符，是在推导中不可以被替代的符号
  3. ->是产生式系统的元符号

结论：

一个语言，可以使用不同的产生式组合来产生。

注意：

D->0|1|2|3|4|5|6|7|8|9不能简写为D->0|…|9

eg：算术表达式的形成规则

E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|I
I->L|IL|ID
L->a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z
D->0|1|2|3|4|5|6|7|8|9

注意：其中E代表表达式，T代表项，F代表因子，先因子再乘除最后加减

注：这是算术表达式，不包含关系表达式的定义（<、<=、>、>=、< >、=），并且标识符没有考虑下划线和大写字母

文法

定义：

文法G是一个四元式，G=（VT ，VN ，S ，P ）

VT 是有限字符的集合，元素称为字母或者终结符

VN 是有限字符的集合，元素称为变量或非终结符

S∈V，称为文法的开始符号

P是产生式α->β的集合

α∈(VT U VN )^+^ ，至少包含一个非终结符

β∈(VT U VN )^*^

α->ε，称为空串产生式或者ε产生式

推导（派生）

定义：文法G，α和β是集合(VT ∪VN )上的串，α= pvr ，β=pur(p和r可能同时为ε)，而v→u是的一个产生式，则称α直接推导出β，记为α=>β ，即pvr =>pur。

术语：

y=>^+^ z 多步推导
y=>^*^ z 任意步推导（多了y=z的情况）

S=>^^ ω 则ω是文法的一个句型
进一步若ω∈VT ^^ ，ω称为句子

L(G) ={ω|S=>^+^ ω，且ω∈VT*} ，则L（G）称为文法G产生的语言

一个语言可以由多个不同的文法产生
一个文法只能产生一个语言

eg：

产生语言L（G）= { a^n^ b^n^ c^n^ |n>0} 文法

解一：

S→aSBC ①
S→aBC ②
CB→BC ③
aB→ab ④
bB→bb ⑤
bC→bc ⑥
cC→cc ⑦

解二：

S→abc|aSBc
cB→Bc
aB→ab
bB→bb

类似思想还可以写出很多文法