Home
Login
updated:

编译原理前端基础知识

<!--toc-->

自动机

文法

形式定义

对于一个文法G=(VT,VN,P,S)G = (V_T, V_N, P, S)，其中

  • VTV_T为终结符的集合

  • VNV_N为非终结符的集合

  • PP为定义在VTV_T和VNV_N上的产生式的集合，有

    A→α∈P,A∈(VT∪VN)+,α∈(VT∪VN)∗,A∩VN≠∅A \rightarrow \alpha \in P, A \in (V_T \cup V_N)^+, \alpha \in (V_T \cup V_N)^*, A \cap V_N \ne \emptyset

  • S∈VNS \in V_N为开始符号，对于自上而下分析法，SS是解析的起点，对于自下而上分析，它是归约的终点

句型与句子

对于文法中的一个产生式A→αA \rightarrow \alpha，假如又有α=γBσ,B→β\alpha = \gamma B \sigma, B \rightarrow \beta，那么可以有A→γβσA \rightarrow \gamma\beta\sigma，那么AA可以推导出γβσ\gamma\beta\sigma，γβσ\gamma\beta\sigma可以归约到AA。

我们可以简记推导关系为

  • A⇒∗α,α∈(VT∪VN)∗A \Rightarrow^* \alpha, \alpha \in (V_T \cup V_N)^*，若AA可以通过0步或多步推导出α\alpha

  • A⇒+α,α∈(VT∪VN)∗A \Rightarrow^+ \alpha, \alpha \in (V_T \cup V_N)^*，若AA可以通过1步或多步推导出α\alpha

  • A⇒nα,α∈(VT∪VN)∗A \Rightarrow^n \alpha, \alpha \in (V_T \cup V_N)^*，若AA可以通过nn步推导出α\alpha

对于一个文法GG，SS为其开始符号，那么假如有

S⇒∗α,α∈(VT∪VN)∗S \Rightarrow^* \alpha, \alpha \in (V_T \cup V_N)^*

那么称α\alpha是GG的一个句型，特别的，假如α\alpha完全由终结符号构成，即α∈VT∗\alpha \in V_T^*，那么α\alpha是一个GG的句子。

若对于一种程序语言LL有一个文法GG，那么使用该语言写成的所有程序都是该文法的句子，形式表示为：

L(G)={α∣S⇒+α∧α∈VT∗}L(G) = \{\alpha \mid S \Rightarrow^+ \alpha \land \alpha \in V_T^*\}

乔姆斯基谱系

当我们向文法中的产生式上施加限制，文法的表达能力将会下降，但解析将会更加容易。根据限制的不同，将文法大致分为以下几类：

  • 0型文法：不对产生式施加任何限制

  • 1型文法：上下文有关文法，需满足

    ∀α→β∈P,∣α∣≤∣β∣∨(α=S∧β=ϵ)\forall \alpha \rightarrow \beta \in P, |\alpha| \le |\beta| \lor (\alpha = S \land \beta = \epsilon)

    注意该文法允许产生式的左侧附带上下文信息。例如保证某个非终结符只有跟在某个终结符后时才能被翻译αA→...\alpha A \rightarrow ...

  • 2型文法：上下文无关文法（表示大部分语言的语法规则，即单词之间如何连接）

    ∀A→β∈P,A∈VN,β∈(VT∪VN)∗\forall A \rightarrow \beta \in P, A \in V_N, \beta \in (V_T \cup V_N)^*

    上下文无关文法要求产生式的左侧只有一个非终结符。

  • 3型文法：正则文法（表示大部分语言的词法规则，即字符如何构成单词）

    ∀A→αB∈P,A,B∈VN∧α∈VT∗\forall A \rightarrow \alpha B \in P, A, B \in V_N \land \alpha \in V_T^*

    或者

    ∀A→Bα∈P,A,B∈VN∧α∈VT∗\forall A \rightarrow B \alpha \in P, A, B \in V_N \land \alpha \in V_T^*

FIRST与FOLLOW

对于一个上下文无关文法GG，文法中每一条产生式PP左侧的文法符号A∈ANA \in A_N都有一个FOLLOW集，代表可能跟在该文法符号后的所有终结符，右侧的每一个文法符号α∈(AN∪AT)∗\alpha \in (A_N \cup A_T)^*都有一个FIRST集，集合中的元素是所有可能出现在该文法符号开头的终结符。

形式定义

FIRST集：

∀A→α∈P,FIRST(α)={a∣α⇒∗aβ,a∈VT}\forall A \rightarrow \alpha \in P, FIRST(\alpha) = \{a \mid \alpha \Rightarrow^* a\beta, a \in V_T\}

特别的，当α⇒∗ϵ\alpha \Rightarrow^* \epsilon时，ϵ∈FIRST(α)\epsilon \in FIRST(\alpha)

FOLLOW集：

∀A→α∈P,FOLLOW(A)=a∣α⇒∗aβ,a∈VT\forall A \rightarrow \alpha \in P, FOLLOW(A) = {a \mid \alpha \Rightarrow^* a\beta, a \in V_T}

自上而下分析

基本原理

例如文法（这里用_来代笔ϵ\epsilon）

E -> aE | F
F -> bF

自上而下分析即以文法符号为根结点构建分析树，自根结点往下进行，使最终叶子结点对应的字符串符号连接起来恰好是输入字符串。

假设有输入流abbb，那么有最左推导（总是替换产生式最左边的文法符号）

abbb: E
 bbb: E -> aE
 bbb: E -> F
  bb: F -> bF
   b: F -> bF
    : end

当输入流中的符号被耗尽时，解析完成，这暗示我们的算法最好能稳定的消耗输入流中的符号。

左递归消除

在一些坏情况下，我们可能会遇到下面的文法：

E -> E + E
E -> ident

这时我们的分析程序可能会重复运用第一条产生式，产生死循环。这种情况称为左递归，因此为了分析算法可以停机，我们需要进行左递归消除。

左递归消除的基本思想是将产生左递归的文法符号替换为一个必然会消耗输入的文法符号，在本例中，E可能以ident开头，因此可以将其替换为

E -> ident + E

在一些更复杂的情况下，例如：

P -> A
A -> AR
A -> ident
R -> [A]

可以看到A -> AR中右侧的A产生了左递归，可以看到A只以ident开始，而且后面跟着的都是R，对其进行推导，我们将会得到形如

A -> AR
  -> ARR
  -> ARRR
  -> AR...R

因此我们可以将原式替换为

P -> A
A -> identA'
A' -> RA' | _
R -> [A]