编译原理：高级语言形式化

发表于 更新于 分类于

文法

描述语言的语法结构的形式规则

字母表（∑\sum）：

  • 集合
  • 非空
  • 有穷

符号：字母表中的元素

符号串（字）：符号构成的一个有穷序列

空字 ε\varepsilon：不包含任何符号的序列

φ\varphi：不含任何元素的空集

闭包

集合 Σ\Sigma 的闭包 Σ∗\Sigma^* 与正闭包 Σ+\Sigma^+ ，基于字母表 Σ\Sigma 的全体符号串

设 Σ={a,b}\Sigma = \{a,b\} 则：

  • 正规闭包：Σ+=a,b,aa,ab,ba,bb,aaa,...\Sigma^+ = {a, b, aa, ab, ba, bb,aaa, ...}
  • 闭包：Σ∗=Σ+∪{ε}\Sigma^*=\Sigma^+\cup\{\varepsilon\}

如果 Σ\Sigma 原来没空字，则正规闭包中没有空字

上下文无关文法

G=(VT,VN,S,P)G=(V_T,V_N,S,P)

VTV_T 终结符（非空），VNV_N 非终结符（非空），VT∩VN=ϕV_T \cap V_N = \phi，SS 文法的开始符号，PP 产生式集合（有限）

产生式

P→αP\rightarrow\alpha

P∈VNP\in V_N, α∈(VT∪VN)∗\alpha \in (V_T \cup V_N)^*（也就是由终结符和非终结符组成的任意字符串）

产生式表达的是从非终结符转化终结符

设 S 为开始符号，S 必须在某个产生式的左部出现一次

注意：上下文无关文法的产生式的左边为 单个 非终结符

BNF

P→α1∣α2∣α3∣...P \rightarrow \alpha_1 | \alpha_2|\alpha_3|...

推导

若存在产生式

A→γA\rightarrow \gamma

则满足：

αAβ⇒αγβ\alpha A \beta \Rightarrow \alpha\gamma\beta

→\rightarrow 代表定义，⇒\Rightarrow 代表直接推出\Rigtarrow

如果

α1⇒α2⇒α3⇒α4⇒...⇒αn\alpha_1 \Rightarrow \alpha_2 \Rightarrow \alpha_3 \Rightarrow \alpha_4 \Rightarrow ... \Rightarrow \alpha_n

则称 α1\alpha_1 可以推导出 αn\alpha_n。其中每一次变化都是直接推出

基于文法 G 的语言 L(G)

L(G)={α∣S⇒+α,α∈VT∗}L(G) = \{\alpha | S\xRightarrow{+}\alpha,\alpha \in V_T^*\}

⇒+\xRightarrow{+} 代表可以从 S 开始经过一步或多步(≥1\geq1)推导出

⇒∗\xRightarrow{*} 代表可以从 S 开始经过0步或多步(≥0\geq0)推导出

最左推导：任何一步 α⇒β\alpha \Rightarrow \beta 都是对 α\alpha 中的最左非终结符进行替换

最右推导：任何一步 α⇒β\alpha \Rightarrow \beta 都是对 α\alpha 中的最右非终结符进行替换

句子、句型、短句、直接短句、句柄

G=(VT,VN,P,S)S⇒∗αAγG = (V_T,V_N,P,S) \\ S \xRightarrow{*} \alpha A \gamma

若S⇒∗BS \xRightarrow{*} B ，则称 B 为一个句型 （就是可以由开始符号推出来的任意串包括开始符号本身）

仅含终结符号的句型为句子 （就是可以由开始符号推出，且只有终结符号）

若 A⇒+βA \xRightarrow{+} \beta，则 β\beta 是句型 αβγ\alpha\beta\gamma 相对于非终结符 A 的短语

若 A⇒βA \Rightarrow \beta，则 β\beta 为直接短语

句柄：一个句型的最左直接短语

归约

推导的逆过程

α⇒ββ⇒.α\alpha \Rightarrow \beta \\ \beta\xRightarrow{.}\alpha

  • 最左规约
  • 最右规约

语法树与二义性

用一张图表示一个句型的推导，这张图称为语法树，也称为推导树

image-20220103165411534

二义性：文法存在某个句子对应两棵不同的语法树

  • 无法在有限时间内判断是否具有二义性
  • 有判断无二义性的充分非必要条件

若一个文法无二义性，对一个句型的多种推导，采用的各种推导过程，画出来的语法树是一样的。语法树并没有描述具体的推导过程，是不同推导过程的抽象共性。

子树：语法树中的一个节点及其 全部 后裔

短语：子树末端形成的符号串

直接短语：简单子树（只有二级）末端形成的符号串

句柄：位于最左边的简单子树的所有叶节点自左向右排列

乔姆斯基对语言的分类

G=(VT,VN,S,P)G = (V_T,V_N,S,P)

产生式形如：

α→β\alpha \rightarrow \beta

0 型

α,β∈(VT∪VN)∗\alpha,\beta \in (V_T \cup V_N)^*

且 α\alpha 至少含有一个非终结符号

1 型 （上下文有关）

∣α∣≤∣β∣，仅S→ε例外|\alpha| \leq |\beta|，仅S\rightarrow\varepsilon例外

2型（上下文无关）

A→βA∈VN;β∈(VT∪VN)∗A \rightarrow \beta \\ A \in V_N;\beta \in(V_T\cup V_N)^*

3 型（正规文法、有限自动机）

右线性文法：

A\rightarrow\alpha B \or A\rightarrow\alpha \\ \alpha \in V_T^* ; A,B\in V_N \\

左线性文法：

A\rightarrow B\alpha \or A\rightarrow\alpha \\ \alpha \in V_T^* ; A,B\in V_N \\

总结

0 型只要求产生式左边包含非终结符

1 型还要求左边的长度要小于右边的长度

2 要求左边只能由一个非终结符组成

3 型要求右边如果有非终结符，只能出现在最左或最右