词法分析器 | 输入源程序,进行词法分析,输出单词符号。 |
---|---|
语法分析器 | 对单词符号串进行语法分析,识别出各类语法单位 |
语义分析与中间代码产生器 | 按语义规则对归约出的语法单位进行语义分析并翻译成中间代码。 |
优化器 | 对中间代码进行优化处理 |
目标代码生成器 | 把中间代码翻译成目标程序 |
表格管理 | 登记源程序的各类信息和编译各阶段的进展情况 |
出错处理 | 对出现在源程序中的错误进行处理 |
乔姆斯基(Chomsky)把文法分成四种类型,即0型、1型、2型和3型。0型强于1型,1型强于2型,2型强于3型。这几类文法的差别在于对产生式加不同的限制。
2. 上下文无关法 一个上下文无关法G是一个四元式G=(V_T,V_N,S,P) ,其中 V_T :终结符集合(非空) V_N :非终结符集合(非空),且V_T\cap V_N=\varnothing
S:文法的开始符号,S\in V_N
P:产生式集合(有限),每个产生式形式为
,开始符S 至少必须在某个产生式的左部出现一次。
句型、句子 假定G是一个文法,S是它的开始符号,称S\overset{*}{\implies}\alpha 是一个句型,称仅含终结符的句型是一个句子。 btw,符号\overset{*}{\implies} 指经过0步及以上推导;符号\overset{+}{\implies} 指经过1步及以上推导;终结符指最终出现在程序中符号;非终结符是为了描述语法而创造出来的符号,不会出现在程序中。 例(i*i+i) 是文法G(E):E→i|E+E|E*E|(E) 的一个句子,证明:
4. 语言 文法G所产生的句子的全体就是一个语言,记为L(G),L(G)=\{\alpha|S\overset{+}{\implies}\alpha\&\alpha\in{V_{T}^{*}}\} 。 例文法G1:A→c|Ab的语言L(G1)={cbn|n≥0}; 文法G2:S→AB,A→aA|a,B→bB|b的语言L(G2)={ambn|m,n≥1}。
结点代表状态,用圆圈表示。状态之间用箭弧连结。箭弧上的标记(字符)代表在射出节点状态下可能出现得输入字符或字符类。 其中0为初态,2为终态(用双圈表示)。终态结上打个星号*意味着多读进了一个不属于标识符部分得字符,应把它退还给输入串。 令\Sigma=\{A,B,0,1\}
2 确定有限自动机(DFA) 一个确定有限自动机M是一个五元式M=(S,\Sigma,\delta,s_0,F) ,其中
S:有穷状态集 \Sigma :输入字母表(有穷) \delta :状态转换函数,为 S×Σ→S 的单值部分映射,\delta(s, a)=s’ 表示:当现行状态为s ,输入字符为a 时,将状态转换到下一状态s’ 。我们把s’ 称为s 的一个后继状态。
s_0\in S:初态(唯一) F⊆S :终态集(可空)
3.非确定有限自动机(NFA) 一个非确定有限自动机M是一个五元式M=(S,\Sigma,\delta,S_0,F) ,其中 S :有穷状态集
\Sigma:输入字母表(有穷)
\delta:S×Σ∗→2S
S0⊆S:初态集(非空)
F⊆S :终态集(可空)
4.LEX LEX用来描述和自动产生所需的各种词法分析器,包括正规式定义和识别规则两部分,将LEX程序编译后所得结果程序记为L,其作用同有限自动机一样,可用来识别和产生单词符号。
(a)确定化
如({0},a)={0,1}表示{0}只经过弧a可以到达{0,1},以此类推。
给状态编号
最小化 终态{0,1},非终态{2,3}
I | Ia | Ib |
---|---|---|
{0,1} | {1} | {2} |
{2,3} | {0,3} | {3} |
{0,1}包含了{1}和{2},所以不能再划分; {0,3}不包含在{0,1}或{2,3}中,拆分由状态2经弧a到达状态0和由状态3经弧a到达状态3,即{2,3}\implies {2},{3}; 得{{0,1},{2},{3}}
(b)已经确定化,进行最小化 终态{0,1},非终态{2,3,4,5}
I | Ia | Ib |
---|---|---|
{0,1} | {1} | {2,4} |
{2,3,4,5} | {0,1,3,5} | {2,3,4,5} |
{2,4} | {0,1} | {3,5} |
{3,5} | {3,5} | {2,4} |
{0,1,3,5}已经大于{0,1}了,故不继续分析
{1}和{2,4}包含于{0,1}、{2,3,4,5},故{0,1}不拆分;
{0,1,3,5}没有包含于{0,1}、{2,3,4,5};又状态24经弧a到达状态10,包含于{0,1},应拆24为一组(其他拆法可自验证),即拆分{2,3,4,5}为{2,4}、{3,5}
{{0,1},{2,4},{3,5}}
I | Ia | Ib |
---|---|---|
{0,1} | {1} | {2,4} |
{2,4} | {0,1} | {3,5} |
{3,5} | {3,5} | {2,4} |
继续验证不可再拆,且都属于集合{{0,1},{2,4},{3,5}}。
P→βP′
P ′ → α P ′ ∣ ε
2.消除回溯 确保对输入符号准确的指派一个候选去执行任务且此候选的工作结果是确信无疑的,避免回溯推倒重来费时费力。
3. First集和Follow集
为: FIRST(\alpha)=\{a|\alpha\overset{*}{\implies}a...,a\in V_T\}
4.LL(1)文法 ①文法不含左递归 ②对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交 即,若A → α 1 ∣ α 2 ∣ . . . ∣ α n 则F I R S T ( α i ) ∩ F I R S T ( α j ) = Φ ③对文法中的每个非终结符A,若它存在某个候选首符集合包含\varepsilon ,则FIRST(A)\cap FOLLOW(A)=\varPhi 文法G满足以上条件,则称G为LL(1)文法。
5. LL(1)基本思想 顾名思义,第一个L表示从左到右扫描输入串,第二个L表示最左推导,1表示分析时每一步只需向前查看一个符号。即根据输入串的当前输入符号来唯一确定选用哪个产生式来进行推导,从而消除左递归和回溯。
6. 递归下降分析优缺点
优点 | 缺点 |
---|---|
分析高效(线性时间) | 频繁递归工作效率低 |
错误定位和诊断信息准确 | 缺乏完善语法检查和出错处理 |
容易实现(方便编码) |
i | + | |
---|---|---|
E | E→TE’ | |
E’ | E’→TE’ |
太多了不想画,举一反三
初始时栈内是#E,例输入串为i,则根据表格栈顶元素E遇到i时,用TE’替代E,即逆序入栈,此时栈内为#E’T,以此类推,当输入串和栈顶都是#(结束符号)时表示成功,如果遇到分析表是空白的,则报错,如果是替换\varepsilon ,则意味不入栈。
(
插播反爬信息)博主CSDN地址:https://wzlodq.blog.csdn.net/
8.下面文法中,那些是LL(1)的,说明理由。
(1)
S→Abc
A → a ∣ ε
B → b ∣ ε
是,满足三个条件
(2) S→Ab
A → a ∣ B ∣ ε
B → b ∣ ε
FIRST(A)∩ \cap∩FOLLOW(A)={b}
FIRST(B)∩ \cap∩FOLLOW(B)={b}
不是,A、B不满足条件③
(3) S→ABBA
A → a ∣ ε
B → b ∣ ε
FIRST(A)∩ \cap∩FOLLOW(A)={a}
FIRST(B)∩ \cap∩FOLLOW(B)={b}
不是,A、B不满足条件③ (4) S→aSe∣B
B → b B e ∣ C
C → c C e ∣ d
FIRST | FOLLOW | |
---|---|---|
S | {a,b,c,d} | {#,e} |
B | {b,c,d} | {#,e} |
C | {c,d} | {#,e} |
FIRST(aSe)∩ \cap∩FIRST(B)=Φ \varPhiΦ
FIRST(bBe)∩ \cap∩FIRST(C )=Φ \varPhiΦ
FIRST(cCe)∩ \cap∩FIRST(d)=Φ \varPhiΦ
是,满足三个条件
其实没有可以不用求FOLLOW集。
6. LR(1)分析过程
(1)sj 把下一状态j和现行输入符号a移进栈; (2) rj 按第j个产生式进行归约; (3)acc 接受; (4)空白格 出错标志,报错 利用图5.5 分析表,假定输人串为i*i+i ,LR分析器的工作过程(即,三元式的变化过程)如下:
7. LR(0)分析过程: 考虑文法
S→AS∣b
A → S A ∣ a
(1)列出这个文法的所有LR(0)项目。
0 S ′ → ⋅ S
1 S ′ → S ⋅
2 S → ⋅ A S
3 S → A ⋅ S S
4 S → A S ⋅ S
5 S → ⋅ b S
6 S → b ⋅ S
7 A → ⋅ S A
8 A → S ⋅ A
9 A → S A ⋅
10 A → ⋅ a
11 A → a ⋅ (2)构造这个文法的LR(0)项目集规范族及识别活前缀的DFA。
确定化
项目集规范族为C=\{I_0,I_1,I_2,I_3,I_4,I_5,I_6,I_7\}
属性文法、综合属性、继承属性 属性文法(也称属性翻译文法)是在上下文无关文法的基础上为每个文法符号(终结符或非终结符)配备若干相关的“值"(称为属性)。.
这些属性代表与文法符号相关信息,例如它的类型、值、代码序列、符号表内容等等。属性与变量一样,可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则,称为语义规则。
综合属性:自下而上传递信息 继承属性:自上而下传递信息 要特别强调的是:
中间代码生成对编译器构造的意义
代码优化的原则
代码生成器的输出是目标程序,目标程序有哪几种形式?