网站只做五周,网站建设对于企业发展的优势,自己如何创建一个网站,百度网站推广一年多少钱这里写自定义目录标题 编译器概念Interpreter and Compiler 解释器和编译器 编译器工作流程 词法分析 Lexical Analysis字母表#xff0c;字符串和语言正则表达式 Regular ExpressionsAtomic Regular Expressions 原子正则表达式Compound Regular Expressions 复合正则表达式 … 这里写自定义目录标题 编译器概念Interpreter and Compiler 解释器和编译器 编译器工作流程 词法分析 Lexical Analysis字母表字符串和语言正则表达式 Regular ExpressionsAtomic Regular Expressions 原子正则表达式Compound Regular Expressions 复合正则表达式 Finite Automata 有限自动机有限自动机图示NFA和DFA 正则表达式转换为NFANFA转化为DFAMinimizing DFA 最小化DFAConfliction Resolutions 冲突解决 Syntax Analysis 语法分析Context-Free Grammars 上下文无关文法定义 推导Derivation传递闭包Sentence句子Parse Trees语法分析树最左推导 LeftMost Derivation最右推导抽象语法树 Abstract Syntax TreesAST二义性ambiguity 自顶向下分析 Top-Down ParsingFirst集Follow集 LL1文法LL1文法定义判定LL1文法方法(重点可空非终结符集合的计算计算First集计算每个非终结符的Follow集通过LL(1)文法定义来识别LL1文法 将非LL1文法转化为LL1文法左公因子左递归消除左递归 Left Recursion Removal消除左公因子 Left Factoring 递归下降分析 Recursive-Descent Parsing构造递归下降分析的过程1. 消除G的左递归或左公因式成为G2. 判断G是否符合LL1文法3. 构造G的递归下降分析 LL1分析 LL(1) parsingLL1分析流程LL1分析表构造LL1分析表 自底向上分析自底向上分析概述主要思想自底向上分析的实现自下而上解析的特点右句型Viable Prefix 可行前缀句柄小结 LR ParsingParsing Table Finite Automata of LR(0) Items and LR(0) Parsing LR0 项的有穷自动机和 LR0 分析解析LR(0) items 难点通过LR0项的集合直接构造DFA重点闭包操作goto操作DFA的构造构造LR0分析表 SLR1ParsingSLR1消除冲突构造SLR1分析表 语义分析 Semantic Analysis语义分析概述属性与属性文法依赖图和属性计算 Dependency Graphs and Algorithms for Attribute Computation掌握依赖图 Dependency GraphsSynthesized and Inherited Attributes 综合属性和继承属性综合属性 Synthesized Attribute继承属性 Inherited Attribute 中间代码生成 Intermediate code generation三地址码 Three-Address Code代码生成技术控制语句和逻辑表达式的代码生成控制语句代码生成包含逻辑表达式的代码生成 这是上学期编译原理的归纳总结为非正式版函待完善
编译器
概念
编译器是将程序从一种语言翻译成另一种语言的计算机程序
Interpreter and Compiler 解释器和编译器
编译器工作流程 词法分析扫描识别描述的逻辑片段。语法分析解析确定这些片段之间的相互关系。语义分析识别整体结构的含义。中间代码生成设计一种可能的结构。中间代码优化简化预期结构。代码生成制造结构。优化改进生成的结构。
词法分析 Lexical Analysis
将物理描述转换为tokens串token为有意义的字符序列Token 表示某种字符模式例如标识符必须以字母开头并且仅包含字母和数字
扫描流程
读取字符流将字符分组到lexemes词素序列中。
Each token is associated with a lexeme.
Each token may have optional attributes. 选择有用的tokens
为关键字提供自己的token。为不同的标点符号punctuation symbols提供自己的token。将表示标识符、数字常量numeric constants、字符串等的词素分组到自己的组中。丢弃不相关的信息空格、注释
字母表字符串和语言
Alphabet 字母表 符号的有限集合如 ∑{0‚1} , Α{a‚b,c} String 字符串 符号的有限序列其中符号取自字母表0,00,10 are strings of ∑{0‚1} a, ab, aaca are strings of Α{a‚b,c} 空串 ε(叫做epsilon) {ε} 不等于空集 Language 语言 在某一个字母表上字符串的任意集合就是语言空集和{ε} 也是Language
正则表达式 Regular Expressions
Regular expressions are a family of descriptions that can be used to capture certain languages (the regular languages). 正则表达式是可用于捕获某些语言常规语言的一系列描述。 Often provide a compact and human-readable description of the language. 通常提供紧凑且人类可读的语言描述。
Atomic Regular Expressions 原子正则表达式
符号ε是正则表达式与空字符串匹配。 对于任何符号 a符号 a 是仅匹配 a 的正则表达式。
Compound Regular Expressions 复合正则表达式
如果 R1 和 R2 是正则表达式则 R1R2 是表示 R1 和 R2 语言的串联concatenation的正则表达式。 如果 R1 和 R2 是正则表达式则 R1 |R2 是表示 R1 和 R2 并集union的正则表达式。 如果 R 是正则表达式则 R* 是 R 的 Kleene 闭包的正则表达式。 如果 R 是正则表达式则 R 是与 R 具有相同含义的正则表达式。
优先级R R* R1R2 R1 |R2 So ab*c|d is parsed as ((a(b*))c)|d
其他标志 大括号(0|1){4} 代表有四个0或1 问号1*0?1* 1*(0 | ε)1* 表示0个或1个 中括号选择其中的一个数字或字母[A-Za-z] 一个任意字母[0-9]一个任意数字 加号表示1个或多个
Finite Automata 有限自动机 NFAs (nondeterministic finite automata),DFAs (deterministic finite automata),
有限自动机图示 只要至少到一个接受状态自动机就被接受结束
ε-transitions自动转换不消耗输入
NFA和DFA
Nondeterministic Finite Automata NFA在给定状态下一个输入可以有多个转换可以有epsilon-transitionDeterministic Finite AutomataDFAOne transition per input per state 每个状态每个输入一个转换。不能有 epsilon-transition
模拟NFA 跟踪一组当前状态最初是开始状态以及ε移动可到达的所有内容。 对于输入中的每个字符维护一组下一个状态最初为空。 对于每个当前状态遵循用当前字母标记的所有过渡将这些状态添加到下一个状态集。将可通过ε移动到达的每个状态添加到下一个状态集。 复杂度Omn2 表示长度为 m 的字符串和具有 n 个状态的自动机。
DFA每个状态必须为每个字母定义一个转换不允许ε移动。
DFA的两种表示方法 在字符串上运行DFA的时间复杂度Onn代表字符串的长度
正则表达式转换为NFA
目的是分解到每个箭头上面只有一个字符标记转换流程 任何长度为 n 的正则表达式都可以转换为具有 On 状态的 NFA。 可以确定长度为 m 的字符串是否与时间 Omn2 中长度为 n 的正则表达式匹配
NFA转化为DFA
我们如何确定哪些词素与每个标记token相关联 当有多种方法可以扫描输入时我们如何知道要选择哪一种 解决方案是使用DFA scanner
回顾一下DFA的特性
每个状态必须为每个字母定义一个转换。不允许ε移动。
子集构造 NFA 可以同时处于多个状态而 DFA 一次只能处于一个状态。 关键思想让DFA模拟NFA。 使 DFA 的状态对应于 NFA 的状态集。 DFA 状态之间的转换对应于 NFA 中状态集之间的转换。
转化步骤 1.1. 消除ε-transition 1.2 消除同一个状态出发的同一字符的转化 2.子集构造 使用 DFA 的一种状态来替换通过从单个输入字符上的状态转换而达到的 NFA 状态集
3.1 建立ε-closure 闭包
3.2 I a I_a Ia 子集 I 是一组状态a 是字母表中的字符
难以理解看看例子 I a I_a Ia 子集就是从a的下一状态开始找闭包 I b I_b Ib 子集就是从b的下一状态开始找闭包
4.从给定的 NFA M 构造 DFA M’的算法
计算 M 的开始状态的ε_closure这成为 M’ 的开始状态对于这个集合以及每个后续集合 S我们计算每个字符 a∈Σ 上的转换 Sa这定义了一个新的状态和一个新的转换继续此过程直到不创建新的状态或转换。M’中那些包含接受状态 M 的状态标记为接受 图中T4包含10接受状态所以后面状态T4是接受状态
Minimizing DFA 最小化DFA
要把状态的数量最小化
它们都是正则表达式 a* 的 DFA但后者是最小的 理论给定任何 DFA都有一个等效的 DFA其中包含最小数量的状态并且此最小状态 DFA 是唯一的
等效状态概念 如果 s 和 t 是两个状态则它们等价当且仅当 - s和t都是可接受或者不可接受状态 - 对于每个字符a∈ΣΣ代表字符表集合s 和 t 在a上具有到等效状态的转换
例子 C 和 F 都是接受状态。它们在“a”到 C 上有过渡在“b”到 E 上有过渡所以它们是等效状态 S 是不接受状态C 是接受状态。它们不是等效状态 状态最小化算法 将状态集拆分为一些不相交的集合因此一个集合中的状态彼此等效而不同集合的任意两个状态是可区分的。
最小化的步骤 1.将状态集分成两组一组由所有接受状态组成另一组由所有不接受状态组成。 2.考虑每个子集的字母表的每个字符“a”上的转换确定子集中的所有状态是等效的还是应该拆分子集。 2.1 如果一个子集中有两个状态 s 和 t它们在不同的集合中具有转化的 ‘a’ 上我们说 ‘a’ 区分状态 s 和 t 2.2 所考虑的状态集必须根据其 a 转换所在的位置进行拆分 3. 继续此过程直到所有集合都只包含一个元素原始 DFA 最小或直到不再发生集合的进一步拆分。
例子1 将下图中的NFA转化为DFA
1.分为接受状态集和不接受状态集 {SAB}{CDEF} 2 继续拆分 通过a拆分{SAB}{S}{A}{B} {CDEF} 3 设 D 代表 {CDEF}
可化成
例子2 1 所有状态都是接受状态{123} 2没有一个状态用b来区分3个状态经过b都到3但a区分状态1与状态2和3{1}{23} 3 {23} 不能用 a 或 b 来区分
Confliction Resolutions 冲突解决
如何确定词素和token的关联方式当有多种方法可以扫描输入时我们如何知道要选择哪一种
Maximal munch 最长前缀匹配priority system 优先级原则
假设所有标记都指定为正则表达式。 从左到右扫描始终匹配其余文本的最长可能前缀Maximal munch规则
如何匹配Maximal munch最长前缀 将表达式转换为 NFA。 并行运行所有 NFA跟踪最后最长的匹配last match。 当所有自动机都卡住时报告最后一个匹配并在该点重新开始搜索。
比如下列匹配如double既满足do又满足double取最长前缀
Syntax Analysis 语法分析
前面词法分析扫出token而语法分析时可以分析恢复token结构
恢复一系列token描述的结构。如果这些token未正确编码结构则报告错误。
语法分析的输入输出 输入解析器调用扫描程序过程来获取下一个token 输出需要构造显式或隐式语法树。语法树的每个节点都包含编译过程其余部分所需的属性 Scanner扫进token后给parser进行解析如果解析正常就继续让scanner获取token Context-Free Grammars 上下文无关文法
字母表是符号的集合∑用作字母。
∑上的语言是一组由∑中的符号组成的字符串。
扫描时我们的字母表是ASCII或Unicode字符。我们产生了token。
解析时我们的字母表是scanner生成的一组tokens
正则表达式无法表达所有集合如 这里没办法保证两边的a的数量相等
正则表达式表达能力不足 无法定义与所有表达式匹配的正则表达式并带有适当平衡的括号。 无法定义与具有正确嵌套块结构的所有函数匹配的正则表达式。
因此引入上下文无关文法上下文无关语法或CFG是编程语言语法结构的规范。与正则表达式类似不同之处在于上下文无关语法涉及递归规则recursive rules是正则语言的超集
例如算术表达式的上下文无关文法 exp即expression的简写op即operator的简写
定义
上下文无关的语法 G V T V_T VT V N V_N VN P S V T V_T VT 是终结符集合。 V N V_N VN是一组非终结符集合 V N V_N VN∩ V T V_T VTφ。P 是一组形式为 A→ α 的产生式或语法规则其中 A∈ V N V_N VN 和 α∈ V N V_N VN∪ V T V_T VTS 是起始符号S∈ V N V_N VN
解释 V T V_T VT 是构成字符串的基本符号。终结符是token V N V_N VN 是表示字符串集的结构的名称以符号“S”表示的字符串集是由语法定义的语言产生式定义一个结构其名称位于箭头的左侧。结构的布局由箭头右侧定义箭头的左侧不能简单地替换为其定义因为定义的递归性质X → Y1 …Yn 表示 X 可以替换为 Y1 …YnX → ε 表示 X 可以用空字符串替换
例子 Notation Conventions 表示法约定
一般第一个产生式的左侧是开始符号使用小写字母表示终结符使用大写字母或包含 … 的名称表示非终结符如果 A→α1A→α2,…,A→αn 都是左边带有 A 的产生式我们可以写成 A→α1|α2|…|αn
注意符号不要与正则表达式混淆应该进行改写不能使用 *、|或括号。
改写1 改写2
四种语法不过只要掌握后面两个即可越往下表示范围越小
推导Derivation
推导的功能 上下文无关语法规则确定一组语法合法的标记字符串 语法规则通过派生或归约来确定token的合法字符串
Derivation意味着用产生式右侧来替换非终结符
推导的例子
传递闭包 当且仅当存在 0 个或多个推导步骤序列 n0
α α1 且 β αn. 如果 n0, then αβ
设 G 是起始符号为 S 的上下文无关语法。那么G的语言是 S 是 G 的起始符号s 表示任意的标记符号字符串有时称为句子
Sentence句子
S 是 G 的起始符号如果S传递闭包为αα仅包含终结符和非终结符则α是G的sentential form 若w是G的sentential form且w仅包含终结符则w是G的Sentence
例子给定 GLG 可以通过推导获得 则S0S1 00S11 000S11100001111 都是 G 的sentential form 只有00001111是G的句子
例题根据描述写出语法产生式 一种语言由 0 和 1 组成该语言的每个字符串都有相同的 0 和 1 数
Parse Trees语法分析树
定义 解析树是token字符串结构的有用表示形式 解析树直观地表示派生
语法分析树的组成部分
根节点是开始符号叶子结点是终结符或者ε非叶子节点是非终结符如果标签为 A ∈ V N V_N VN 的节点有 n 个标签为 X1X2,…,Xn可能是终端或非终端的子节点则A → X1X2…Xn ∈P
派生可以表示为解析树 对于产生式 X→Y1 …Yn 添加子项 Y1 … Yn 到节点 X
推导和语法分析树 派生不唯一地表示它们构造的字符串的结构而解析树可以
最左推导 LeftMost Derivation
在推导的每个步骤中替换最左边的非终结符的推导相当于前序遍历
示例
最右推导
在推导的每个步骤中替换最右边的非终结符的推导 它对应于解析树的后序遍历的反向 抽象语法树 Abstract Syntax TreesAST
解析树包含的信息比编译器生成可执行代码绝对必要的信息多得多抽象语法树仅包含真正需要的信息 区别AST的运算符在中间节点而不是叶子结点 AST 是用于后续编译阶段的更好结构 抽象语法树表示实际源代码标记序列的抽象 parser将遍历解析树表示的所有步骤但通常只会构造抽象语法树
字符串的语法分析树和抽象语法树
二义性ambiguity
可能一个表达式的最左最右推导的解析数是不同的有二义性ambiguity 因此需要消除二义性规则乘法优先减法左结合
或者重写语法将运算符分组为优先级相等的组对于每个优先级我们必须编写不同的规则。
将语法更改为强制构造正确解析树的形式考试考的少 考试主要考判断是否具有二义性并给出理由画语法树
小结 语法分析解析从扫描程序生成的token中提取结构。 语言通常由上下文无关语法 CFG 指定。 语法分析树显示如何从语法派生字符串。 如果字符串具有多个分析树则语法不明确。 抽象语法树 AST 包含程序语法的抽象表示形式。
自顶向下分析 Top-Down Parsing
parsing语法分析的目标恢复程序的语法结构
自顶向下就是从开始符号开始推导过程大约如下
最终要推导出的是终结符 但是有多个产生式多个推导时如何选择因此要进行Predictive parsing预测解析 两种预测解析的方法 Recursive-descent parsing 递归下降分析 LL(1) parsing
输入字符串的分析以语法的开始符号开头 如果它可以根据输入中的前瞻token唯一地确定下一个在推导中使用哪个产生式则解析是预测性的 Predictive parsers接受 LLk 语法
L means “left-to-right” scan of input从左到右扫描L means “leftmost derivation”最左推导k means “need k tokens of lookahead to predict”需要预读k个词法单元分析预测k大代价大
First集
定义 β可以推导出的所有token当中的首终结符集合 如果β是ε的传递闭包则ε也在β的First集当中 . 简单说就是β的产生式右边的第一个终结符就是First集属性 Follow集 简单来说非终结符A的Follow集就是产生式右边跟在A后面的终结符如果有产生式后面什么都不跟那么$也在Follow集中
例子
Let the current input symbol is “x” 不同情况选择不同的产生式 如果 x ∈FIRSTbAS{b} 则选择 A→bAS 进行派生 如果 x ∈FOLLOWA{$ad } 则选择 A→ε 进行派生 因为 FIRSTbAS∩FOLLOWA Φ 所以可以选择产生式下面有个规则
LL1文法
LL1文法定义
判断是否为LL1文法的两个条件
For each production A → α1|α2|…|αn , for all i and j, 1≤i, j ≤ n, i≠j , First(αi) ∩First(αj) Φ 所有同一符号推出的产生式的右部的First集的元素不重复 For each nonterminal A such that First(A) contains ε, First(A) ∩Follow(A) Φ 对于First集包含ε的所有非终结符则需要First集和Follow集的交集为空
例子判断下列产生式是否符合LL1文法 因为FirstA∩FollowA{b}≠Φ 故G[S] 不是 LL1 语法当最左边要替换的非终端是 A 并且当前输入符号是 “b” 时解析无法确定选择 A 的哪些产生式A→bA 或 A→ε
判定LL1文法方法(重点
a) 计算可空非终结符集合 b 为每个产生式的右侧字符串α计算 FIRST(α)集 c 计算每个非终端 A 的Follow(A) d 根据LL1的定义进行识别
可空非终结符集合的计算
存在一个推导使非终结符A的传递闭包为ε 就证明可空
若U 表示可空的非终结符集合
step 1: U{ Aj | Aj→ ε 是一个产生式} 即将每个直接推出ε的非终结符加入集合当中step 2: 对每个产生式 p: Ap→X1…Xn, if X1…Xn∈U, then U: U∪ {Ap } 当 A p A_p Ap推出来的非终结符全是之前在可空集合里面的非终结符必须X1到Xn都在集合内则 A p A_p Ap加入集合U中 step 3: 重复第二步直到集合U不变
例子
计算First集
First集计算分成计算每个符号的First集和计算串的First集两种这里先介绍计算每个符号的First集合
step1对终结符First集就是本身step2对非终结符看传递闭包传递闭包为ε则First集为ε否则传递闭包为空step3 对于在产生式左侧的非终结符见SecondFirst描述重复step3直到集合不变 步骤
if X1 is not nullable, then SectionFirst(X1…Xj…Xn) First(X1) 第一个符号不可空时所有推出的子串的Fitst集就是X1的first集if X1 is nullable, then SectionFirst(X1…Xj…Xn) First(X1) -{ε}, and continue to see X2. Stop until Xi is not nullable . 若X1可空就一直往后找直到有不可空的if X1…Xn are all nullable, then SectionFirst(X1…Xn) (First(X1) -{ε}) ∪(First(X2)-{ε})∪… ∪(First(Xn) -{ε}) ∪{ε} 若一直找不到可空的就把ε加进First集中
例子
例1 这里关注S和C的First集S推导出AB而A,B均可空因此AB的First本身含的a,b然后再把ε都加进First(S)C推导出ADA可空而D不可空把AD含的a,b,c加进First( C ) 计算产生式右侧的First集
假设αX1X2…Xn要计算First(α)
若X1不可空则直接等于X1的非终结符若X1可空就一直往后找直到有不可空的若找到后面都可空则First集为所有符号的First集加上ε
例2这里计算的是产生式右侧的First集
计算每个非终结符的Follow集
step1S 是起始符号FollowS{$};对于所有 非终结符A和 A≠SFollowA{ };step2对于每个产生式 B→αAγ对于每个非终结符A Follow(A)Follow(A) ∪ (First(γ) -{ε})即在A后面的符号的First集减掉εif ε ∈ First(γ) then add Follow(B) to Follow(A) 如果非终结符后面的符号First集包含ε就要加Follow(B) to Follow(A) step3重复step2直到follow集合不变
例子求每个非终结符的Follow集首先要求出每个符号的First集 这里的GS证明S是起始符号一定有$ 另外产生式右侧非终结符后面没符号也加上$
注意事项
空串ε可以出现在First集但不能出现在Follow集Follow集只是为了非终结符定义的即FollowX中的X只能是非终结符
通过LL(1)文法定义来识别LL1文法 例子判断G[S]是否为LL1文法
将非LL1文法转化为LL1文法
消除left factor左公因子和左递归是LL1文法的必要不充分条件
左公因子
同一个非终结符推出的具有公共前缀这个公共前缀就是左公因子有这个左公因子就不是LL1
左递归
从A开始推导又推出A开头的符号串则为左递归 这里a式子是immediate left recursion立即左递归b式子是indirect left recursion间接左递归推好几次才回到A开头
判断左递归的方法
对于下面的两个左边相同的产生式 一个产生式右边的First集包含另一个产生式右边的First集就是左递归的这里First(Aα)包含First(β)当然直接以A开头的立即左递归本身就很明显
不能保证消除左递归和消除左公因子这些技术的应用会将语法转换为LL1语法转换之后要使用上节手段进行判断
消除左递归 Left Recursion Removal
消除的方法 把 A→Aα1|Aα2|…|Aαm|β1|β2|…|βn 改成 A→β1A’|β2A’|…|βnA’ A’→α1 A’|α2 A’|…|αm A’|ε 即把左递归变成右递归但要加上ε
简单例子 A → Aα| β 改写成 A → βA’, A’ → αA’| ε
复杂例子 这里E和T都有能看出来的直接左递归
消除左公因子 Left Factoring
这个比较简单提公因子就是了 递归下降分析 Recursive-Descent Parsing
为每个将识别 A 的非终结符A 定义一个过程A 的语法规则的右侧指定此过程 A 的代码结构 终结符对应于输入的匹配非终结符对应于对其他过程的调用选项对应于代码中的备选项大小写或 if 语句
构造递归下降分析的过程
1. 消除G的左递归或左公因式成为G’ 2. 判断G’是否符合LL1文法 3. 构造G’的递归下降分析
由一个主过程和一组递归过程组成每个过程对应于语法的非终结符 使用的变量
token是一个变量用于在输入中保留当前的下一个tokenmatch(y)是下一个令牌 TOKEN 与其参数 y 匹配的过程如果成功则推进输入如果不成功则声明错误error是打印错误消息并退出的过程
3.1 “或运算”|的递归下降代码 对于非终结符U如果U → x1 | x2 |…|xn, and x1,…,xn≠ ε则过程U的代码
if TOKEN in First(x1) then p_x1else if TOKEN in First(x2) then p_x2else …….else if TOKEN in First(xn) then p_xnelse ERROR如果产生式包含U → ε 则要把
if TOKEN in First(xn) then p_xn else ERROR改写为
if TOKEN in First(xn) then p_xnelse if TOKEN not in Follow(U) then ERROR3.2 “与”运算的递归下降代码 xy1y2…yn的代码
begin p_y1;p_y2;…;p_yn end如果 yi∈VN 非终结符则p_yi是过程 yi 的调用;否则如果 yi∈VT终结符 则p_yi是matchyi
例 E→TE ’ E’→TE’│ε T→FT ’ T’→*FT’│ε F→(E)│i 1调用开始符号E的main函数
(1) program MAIN; /* main */beginGETNEXT (TOKEN);E ; /* call E */if TOKEN ≠‘$ then ERRORend.2E→TE 的递归下降
(2) procedure E; /*E→TE*/beginT; /*call T*/E’ /*call E’*/end3E’→TE’│ε 这里注意要算E’的Follow集
(3) procedure E’; /*E→TE│ε*/beginif TOKEN’’ then /*E→TE*/beginmatch(‘’);match表示当前必须匹配加号否则不符合语法规则 T; /*call T*/E’ /*call E’*/end else /*E’ → ε*/if TOKEN≠’)’ and TOKEN≠’$’ then ERROR end;4 F→(E)│i
(4) procedure F; /* F→(E)│i */beginif TOKEN ( then /*F→(E) */beginmatch(‘(’); E; /* call E */ match(‘)’)endelse /* F→i */if TOKEN‘i’ then match(‘i’)else error;end;3.3 大括号表示重复的与while关联 递归可以这样改写
E→ T { T}
(1) procedure E;beginT;while token‘’ domatch(‘’);T;end while;end3.4 [ ] 中括号表示可选的出现0次或1次 Example: if-stmt-if (exp) stmt | if (exp) stmt else stmt改写成if-stmt-if (exp) stmt [else stmt]例子
if-stmt → if (Exp) Stmt [else Stmt]
翻译成递归下降代码Procedure ifStmt;beginmatch(‘if’);match(‘(‘);Exp;match(‘)’);Stmt;if token‘else’ then //识别分支match(‘else’);Stmt;end if;end ifStmt;LL1分析 LL(1) parsing
Predictive Parsing的方法一种是递归下降分析一种是LL1分析 LL1分析流程
将开始符号放到栈中如果栈顶是终结符就执行match看栈顶和当前输入是否相同栈顶是非终结符替换。对于A → α产生式先把A弹出去然后反向把α压进去比如α 代表bc先把c压进去栈顶和输入串同时到结束标记$时停止
例子
LL1分析表
作用是决定可以用哪个产生式替换非终结符是个二维数组二维表格每一行一个终结符每一列一个非终结符如果 M[Nt] 在构造后保持为空则表示解析过程中可能发生的潜在错误
构造LL1分析表
对每个非终结符 A 和产生式 A → α 重复以下两个步骤 对First(α)集里面每一个token把产生式填进去A直接推出 若A的First集包含空串ε进行第二步 如果ε在First(α)中 对FollowA的每个终结符’a’对应的产生式加进去a可以出现在A后面让A消失后面的a推出
例子要构造左边的语法的LL1分析表 1清除左递归清除左公因子 2 计算出所有非终结符的First集合Follow集合
3根据前面所述构造分析表
如果关联的 LL1 分析表在每个表条目每个单元格中最多有一个产生式则语法就是 LL1 语法。
若用该分析表对某个串进行分析过程如下 自底向上分析
自底向上分析概述
主要思想
定义从输入串开始通过归约反向利用产生式最后把token串归约为开始符号 输入字符串是语法分析树的叶子从这开始到开始符号根节点
但重点是确定要使用哪个字符串和产生式归约比如 是两种不同的归约一种可以到S一种不可以
自底向上分析的实现
采用Parsing Stack分析栈自下而上的解析器使用显式堆栈来执行解析
栈中包含token、非终结符和状态比自顶向下的多了个状态自上而下的解析堆栈存储等待在parsing中匹配的符号而自下而上的解析堆栈存储已匹配的符号
自底向上的两种操作
Shift: shift a terminal from the front of the input to the top of the stack 移入将左边的token从输入串移动到栈顶Reduce: reduce a substring α at the top of the stack to a nonterminal A, given the production 归约栈的顶部形成子串就是接下来要归约的子串把产生式右边的α弹出把非终结符A压进去
因此自底向上分析也叫shift-reduce parsing
例子
自下而上解析的特点
Right Sentential Form 右句型 Viable Prefix 可行前缀 Handle 句柄
右句型
A shift-reduce parser traces out a rightmost derivationof the input string in reverse order 最右推导从右向左扫先替换最右边的匹配的非终结符的逆过程就是归约因此规约是从左向右换
最右推导及过程中得到的句型都为右句型
例子 重复从字符串输入移入shift到堆栈直到可以执行归约reduce以获得下一个正确的句子形式
每个右句型是shift-reduce parsing的一个中间结果
Viable Prefix 可行前缀
解析堆栈上的符号序列即Stack那一列出现过的称为右句型的可行前缀
例如 对应的右句型为aAcde则其可行前缀有aA, aAc, aAcd
只要解析堆栈的内容是右子句型的可行前缀shift-reduce parsing就是正确的
句柄
右句型γ句柄是与产生式 A-β的右侧匹配的子字符串β可以替换为 A 以在γ的最右推导中生成以前的右句型 例子根据产生式和给出的串写出字符串的句柄 首先写出开始符号的最右推导最后一步替换出来的子串就是句柄
但是在许多情况下与某些生产 A-β 的右侧匹配的最左侧子字符串β可能不是句柄因为产生式 A-β 的归约会产生不是右句型的字符串。 即不是右句型无法被归约为开始符号
例如
小结
句柄和可行前缀 可行前缀是右句型的前缀从左到右不超过该句型的句柄的右端。 假设右子句型是aAbcde Ab是句柄则可行前缀为a, aA, aAb 句柄与shift-reduce parsing 确定解析器中的下一个句柄是 shift-reduce 解析器的主要任务当下一个句柄位于堆栈顶部时将执行“归约”操作当下一个句柄尚未在堆栈顶部形成时将执行操作“shift” 自下而上分析 与可行前缀和句柄的关系 Parser不断将可行前缀放在堆栈中只要堆栈的内容是可行前缀解析就是正确的当句柄位于堆栈顶部时进行归约 LR Parsing
L indicates that the input is processed from left to right L 表示输入从左到右处理R indicates that a rightmost derivation is produced R 表示生成最右推导K for the number of input symbols of lookahead that are used in making parsing decisions K 表示用于做出解析决策的前瞻输入符号的数
主要的三种
LR0 解析在做出解析决策时不参考前瞻符号SLR(1) parsing (simple LR(1)) is an improvement on LR(0) SLR1 解析 简单 LR1 是对 LR0 的改进 LR(1) parsing is the most powerful and most complex (with one lookahead symbol) LR1 解析是最强大和最复杂的 只有一个前瞻符号
Parsing Table
每行代表一个状态每列是一个语法符号
ACTION: take a state and a terminal symbol, determine the next action to take place 获取状态和终结符确定要发生的下一个操作 GOTO: take a state and a grammar symbol, determine the next state 获取状态和语法符号终结非终结都可确定下一个状态
GOTO的Parsing Table仅保留非终结符就行
Shift(sk) 将符号 ai 和状态 K 放入堆栈中Reduction(rk) 按 k个 产生式 A-γ 减少该操作包括 从堆栈中弹出字符串γ及其所有相应的状态。假设当前堆栈的顶部是状态 Si 将 A 推到堆栈上 将状态 Sj GOTO[SiA] 推到堆栈上Accept 表示解析成功完成Error (Empty) 指示分析已发现错误
例子 这是泛用的Parsing Table
这是利用Parsing table的parsing过程LR Parser
Finite Automata of LR(0) Items and LR(0) Parsing LR0 项的有穷自动机和 LR0 分析解析
使用 LR0 解析表的 LR 解析器是 LR0 解析器;可以构造 LR0 解析表的语法称为 LR0 语法LR0 解析器仅使用堆栈的内容来确定句柄它不需要输入token作为前瞻几乎所有“真正的”语法都不是 LR0但 LR0 方法是学习 LR 解析的良好起点
LR(0) items 难点
我们需要能通过上下文无关文法产生式写出其LR0项
语法 G 的 LR0 项是 G 的产生式其右侧具有可区分的位置
例如产生式 U→XYZ 有四个项 [0] U→ • XYZ [1]U→X • YZ [2] U→XY • Z [3]U→XYZ • 产生式 A→ε只有一个项目 A→• 这些项称为 LR0 项因为它们不包含对前瞻的显式引用
项是记录识别产生式右侧的中间步骤
A→ • βγ 表示我们可能即将通过使用产生式A→ βγ来识别 AA→β • γ表示已经识别了ββ必须出现在堆栈顶部A→ βγ • 表示 βγ 现在位于堆栈的顶部可能是句柄而 A- βγ 将用于下一次归约 LR0 项可以用作有限自动机的状态该状态维护有关解析堆栈和移位-归约解析进度的信息
1 构建 LR0 项的 NFA2 直接构造 LR0 项集合的 DFA重点 在构造 DFA 之前首先通过单个产生式 S‘-S 来增广语法其中 S’ 是一个新的非终结符它成为增广语法的开始符号S’- •S 成为 DFA 启动状态的第一个item
例子
符号 X 从状态 i 到状态 j 的转换
如果 X 是一个标记则此转换对应于解析期间 X 从输入到堆栈顶部的偏移如果 X∈VN则此转换对应于将 X 推送到堆栈上。 它只能在产生式 X→r 的归约期间发生如何构建从一种状态到另一种状态的过渡?----goto 操作
通过LR0项的集合直接构造DFA重点
闭包操作
如果 I 是一组 LR0 项则closureI 是由 I 构造的一组项由以下规则构造
a) 最初closureI I;b) 如果 A-α•Bβ 在closureI中 并且 B ∈VN B是非终结符 则对于每个产生式 B→r将项 B→•r 添加到closureIc) 重复 b 直到不再添加新项
如果**‘ • ’ 在最右端或者后面只有终结符**闭包就是项本身
例子
goto操作
X∈VN∪VT goto(I, X) closure(J) 其中 J 是所有项目 [ A→αX•β] 的集合使得 [A→α• Xβ] 在 I 中 DFA的构造
a) closure({S’→•S}) 是 DFA 的开始状态它是未标记的b) 从 DFA 获取未标记的状态 I S i IS_i ISi 标记 I S i IS_i ISi对于 I S i IS_i ISi 的每个项 U-x•Ry R∈ VN∪VTx 和 y 是字符串计算 g o t o I S i R I S j gotoIS_iRIS_j gotoISiRISj 将 I S j IS_j ISj 添加到 DFA 作为未标记如果不存在在 R 上添加 I S i IS_i ISi 到 I S j IS_j ISj 的转换 c) 重复 b 直到 DFA 中没有未标记的状态
例子
构造LR0分析表
给定一个语法 G我们增广 G 以产生 G’构造 G’ 的 LR0 项集合的 DFA状态 K 的 ACTION 部分确定如下将每个状态映射到一个操作 如果 A→α•β∈K 则 ACTION[K]Shift如果 A→α•∈K归约项并且 A→α 的标号为 j则设置 ACTION[K]Rj 状态 K 的 GOTO 部分将状态/符号对映射到下一个状态是使用以下规则为所有符号构造的如果 gotoKXJ X∈VN∪VT∪{$}则设置 GOTO[KX]J
SLR1Parsing
项的冲突
Shift-Reduce Conflict 移入归约冲突 如果集合包含移入项 A→α•aβ 和完成项complete item B→r•则对于是shift“a”还是将“r”reduce为 B 会出现分歧 Reduce-Reduce Conflict 归约归约冲突 如果一个集合包含完成项complete item A→β•和B→r •则在使用哪个产生式进行reduction方面会出现歧义。 当且仅当项目集中没有 Shift-Reduce 冲突或Reduce-Reduce冲突时才是LR0文法
例子判断是否为LR0文法 SLR1消除冲突
SLR1 解析是 LR0 的简单、有效的扩展使用LR0项的集合构造的DFA通过使用输入字符串中的下一个标记来指导其操作从而提高 LR0 解析的能力它在转换之前查询输入token以确保存在适当的 DFA 转换它使用非终结符的FOLLOW集来决定是否应进行归约 For item A→r•, reduction only takes place when the next token a∈FOLLOW(A) a在A的FOLLOW集里面才能归约 具体消除冲突操作规则 I{X→α•bβ‚Α→r•‚Β→δ•}, where b∈VT if FOLLOW(A) ∩FOLLOW(B)φ and not includes b, the action for I is based on the next input token ‘a’ 如果A和B的FOLLOW集无交集则 I 的操作基于下一个输入标记“a”
If ab, then shiftIf a∈FOLLOW(A), then reduce with A→rIf a∈FOLLOW(B), then reduce with B→δOtherwise, an error occurs
构造SLR1分析表 步骤如下
构造 LR0 项集合的 DFA确定状态K的action部分 a. 如果 A→α•aβ∈K、a∈VT (句点后面是终结符)移入 gotoKaJ把 Sj填入K行a列 b. 如果 A→α•∈K 句点后面没东西并且对应的产生式 A→α 的标号为 j则为每个 b∈FollowA 设置 ACTION[Kb]Rj c. 如果 S’→S•∈K则设置 ACTION[K$]‘acc’状态 K 的 GOTO 部分是使用以下规则为所有非终结符构造的如果 A→α•Bβ∈K、B∈VN 和 gotoKBJ则设置 GOTO[KB]‘J’
例子
语义分析 Semantic Analysis
语义分析概述
语义与正在翻译的程序的最终含义密切相关的信息 语义分析分析编程语言语义规则所需的程序以确定其正确性并保证正确执行
类型检查 运算符的操作数类型是否相等 赋值assignment的左侧和右侧的类型是否相等 形参的类型是否与对应的实参相同 数组的索引类型是否合适
是否已声明使用的标识符 V 是否已声明为“V[E]”的数组类型的变量
构建符号表以跟踪声明中建立的名称的含义 对表达式和语句执行类型检查以确定它们在语言类型规则中的正确性
属性与属性文法
属性的定义属性是编程语言构造的任何属性 属性包括 变量的数据类型 The data type of a variable 表达式的值 The value of an expression 过程的目标代码 The object code of a procedure
属性语法用来描述语义规则
属性直接与语法符号终结符和非终结符相关联
如果 X 是语法符号a 是与 X 关联的属性则与 X 关联的 a 的值写为 X.a
属性 a1,…,ak 的属性语法是语言的所有语法规则的所有属性方程的集合 通常属性语法以表格形式编写 例1无符号数对应的属性语法 无符号数的属性就是值 例2变量声明对应的属性语法. 变量声明的属性就是数据类型
依赖图和属性计算 Dependency Graphs and Algorithms for Attribute Computation掌握
依赖图 Dependency Graphs
给定属性语法每个语法规则都有一个关联的依赖关系图 每个符号的每个属性 Xi.aj 对应一个节点 对于每个属性方程 Xi.ajfij…Xm.ak,…从右侧的每个节点 Xm.ak 到节点 Xi.aj 都有一个边表示 Xi.aj 对 Xm.ak 的依赖性
三个属性语法的依赖关系图
由上下文无关语法生成的合法字符串的依赖关系图是表示字符串解析树的每个节点的语法规则选择的依赖关系图的联合很拗口也就是说多个规则组成一个大规则
Synthesized and Inherited Attributes 综合属性和继承属性
属性评估依赖于解析树的显式或隐式遍历不同类型的遍历在可以处理的属性依赖关系类型方面的能力各不相同根据属性表现出的依赖类型对属性进行分类可以分为 Synthesized attribute 综合属性Inherited attribute 继承属性
综合属性 Synthesized Attribute
依赖关系从下面指向上面儿子节点指向父亲节点等号左边出现小a右边每个产生式都要有k个小a A.afx1.a1,…X1.ak,…,Xn.a1,…Xn.ak
如图val属性是Synthesized Attribute
假设解析树或语法树已由解析器构造 合成的属性值可以通过树的单个自下而上或后序遍历来计算 先计算儿子节点的综合属性再往上算
继承属性 Inherited Attribute
继承的属性具有从解析树中的父级流向子级或从同级流向同级的依赖项 在变量声明的属性文法中dtype是继承属性 继承的属性可以通过解析树或语法树的先序遍历来计算计算T的每个儿子的继承属性从上往下递归算
与综合属性不同由于继承的属性可能在儿子节点属性之间具有依赖关系因此计算子项的继承属性的顺序非常重要
中间代码生成 Intermediate code generation
代码生成的任务是为目标计算机生成可执行代码该代码表示源代码的语义
代码生成通常分为几个步骤 1.Intermediate code generation与机器无关 2.生成某种形式的汇编代码 3.优化提高目标代码的速度和大小
三地址码 Three-Address Code
中间代码有很多种前面说到的抽象语法树也是一种但是与实际代码相去甚远所以这里采用三地址码
三地址码的一般形式y和z进行op运行赋值给x即xy op z 其中xyz 是名称、常量或编译器生成的临时名称x、y和z各代表内存中的一个地址op代表任何算术或逻辑运算符例如 、‘and’
例如2*a(b-3)的三地址码
三地址码只要不超过3个地址就行下面是9种形式
赋值语句的形式为 “xy op z”其中 op 是二进制操作赋值语句的形式为 “xop y”其中 op 是一元运算拷贝语句的形式为 “xy”其中 y 的值赋值为 x“goto L” 无条件跳转指令L代表某一条指令的地址“if B goto L” , “if_false B goto L”有条件就跳转不满足条件BBoolean就不跳转“Label L” 标号定义语句定义后面那句语句的地址“read x”“write x”“halt” 表示三地址码的结束
下面是将源代码改写为三地址码的例子
代码生成技术
生成的三地址代码被视为字符串属性 中间代码成为可以使用属性语法定义并由语法树的后序遍历生成的synthesized attribute合成属性
三地址码的属性语法
tacode for three-address code 表示程序语句或表达式的三地址码属性字符串类型属性name 为表达式中的中间结果生成的临时名称的名称
字符串串联的符号 用于与有换行符的字符串连接|| 用于与有空格的字符串连接
函数 newtemp 返回一个新的临时名称
例子 给定表达式的语法 exp - idexp | aexp aexp - aexpfactor | factor factor - (exp) | num | id 假定令牌 id标识符 和 num整型常量具有预先计算的属性 strval该属性是token的字符串值
对应的属性语法 再改写成三地址码由于三地址码属性是综合属性因此自底向上计算
控制语句和逻辑表达式的代码生成
前面主要是用于赋值和简单算术表达式的代码生成 现在说说控制语句和逻辑表达式的代码生成
逻辑表达式或布尔表达式由应用于布尔变量或关系表达式元素的布尔运算符andornot组成 关系表达式的形式为 “E1 relop E2”其中 E1 和 E2 是算术表达式relop 是一个比较运算符 由以下语法生成的布尔表达式 E-E or E | E and E | not E | (E) | id relop id | true | false or 和 and 是左关联or具有最低优先级not右关联最高优先级
如果布尔表达式用于计算逻辑值则布尔表达式将以类似于算术表达式的方式进行转换
例子 如果将它们用作控制语句上下文中的测试例如 if-then 或 while-do则布尔表达式的值不会临时保存而是由程序中达到的位置表示
控制语句代码生成
下面是控制语句的语法
控制语句上下文中布尔表达式的翻译
E.true (E.false) 表示布尔表达式的真假出口S.next 是S 代码之后要执行的第一个三地址指令的标签S.begin 表示整个S的第一条指令newlabel 每次调用时都会返回一个新标签 类型1S-if E then S1
E.true 是附加到 S1 代码生成的第一条指令 E.false 是附加到 S 代码之后要执行的第一个指令 类型2S-if E then S1 else S2 E.true 附加到 S1 代码的第一条指令 E.false 附加到 S2 代码的第一条指令 类型3S-while E do S1
E.true 附加到 S1 代码的第一条指令 E.false 附加到 S 代码之后要执行的第一个指令 包含逻辑表达式的代码生成
基本形式 例1E - E1 or E2 先判断E1E1.true则E.true 若E1.false则创建新标签判断E2E2的真假出口和E相同 例2E - E1 and E2 例3关系运算ab or cd and ef 假设整个表达式的 true 和 false 出口已设置为 Ltrue 和 Lfalse 例4 下述控制语句的代码生成 文章转载自： http://www.morning.dthyq.cn.gov.cn.dthyq.cn http://www.morning.qkdcb.cn.gov.cn.qkdcb.cn http://www.morning.tddrh.cn.gov.cn.tddrh.cn http://www.morning.lgtcg.cn.gov.cn.lgtcg.cn http://www.morning.pkwwq.cn.gov.cn.pkwwq.cn http://www.morning.jrqcj.cn.gov.cn.jrqcj.cn http://www.morning.qgghj.cn.gov.cn.qgghj.cn http://www.morning.htmhl.cn.gov.cn.htmhl.cn http://www.morning.ljsxg.cn.gov.cn.ljsxg.cn http://www.morning.mhmcr.cn.gov.cn.mhmcr.cn http://www.morning.nkllb.cn.gov.cn.nkllb.cn http://www.morning.ktrzt.cn.gov.cn.ktrzt.cn http://www.morning.nfpkx.cn.gov.cn.nfpkx.cn http://www.morning.hnrdtz.com.gov.cn.hnrdtz.com http://www.morning.ygxf.cn.gov.cn.ygxf.cn http://www.morning.lbjdx.cn.gov.cn.lbjdx.cn http://www.morning.aiai201.cn.gov.cn.aiai201.cn http://www.morning.rrxnz.cn.gov.cn.rrxnz.cn http://www.morning.rzmlc.cn.gov.cn.rzmlc.cn http://www.morning.tsycr.cn.gov.cn.tsycr.cn http://www.morning.pbmg.cn.gov.cn.pbmg.cn http://www.morning.cdrzw.cn.gov.cn.cdrzw.cn http://www.morning.qnftc.cn.gov.cn.qnftc.cn http://www.morning.wlnr.cn.gov.cn.wlnr.cn http://www.morning.dysgr.cn.gov.cn.dysgr.cn http://www.morning.bfysg.cn.gov.cn.bfysg.cn http://www.morning.plqkz.cn.gov.cn.plqkz.cn http://www.morning.bfysg.cn.gov.cn.bfysg.cn http://www.morning.qphgp.cn.gov.cn.qphgp.cn http://www.morning.gassnw.com.gov.cn.gassnw.com http://www.morning.fppzc.cn.gov.cn.fppzc.cn http://www.morning.gryzk.cn.gov.cn.gryzk.cn http://www.morning.sqfrg.cn.gov.cn.sqfrg.cn http://www.morning.mhlsx.cn.gov.cn.mhlsx.cn http://www.morning.fmznd.cn.gov.cn.fmznd.cn http://www.morning.hyxwh.cn.gov.cn.hyxwh.cn http://www.morning.hyhqd.cn.gov.cn.hyhqd.cn http://www.morning.xckdn.cn.gov.cn.xckdn.cn http://www.morning.nytgk.cn.gov.cn.nytgk.cn http://www.morning.dwxqf.cn.gov.cn.dwxqf.cn http://www.morning.bpds.cn.gov.cn.bpds.cn http://www.morning.nnwmd.cn.gov.cn.nnwmd.cn http://www.morning.ppgdp.cn.gov.cn.ppgdp.cn http://www.morning.byywt.cn.gov.cn.byywt.cn http://www.morning.qcsbs.cn.gov.cn.qcsbs.cn http://www.morning.xgbq.cn.gov.cn.xgbq.cn http://www.morning.rrxgx.cn.gov.cn.rrxgx.cn http://www.morning.kqhlm.cn.gov.cn.kqhlm.cn http://www.morning.pqnpd.cn.gov.cn.pqnpd.cn http://www.morning.mhcft.cn.gov.cn.mhcft.cn http://www.morning.wxqmc.cn.gov.cn.wxqmc.cn http://www.morning.mhnb.cn.gov.cn.mhnb.cn http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.ypktc.cn.gov.cn.ypktc.cn http://www.morning.lbywt.cn.gov.cn.lbywt.cn http://www.morning.wxfjx.cn.gov.cn.wxfjx.cn http://www.morning.qwmdx.cn.gov.cn.qwmdx.cn http://www.morning.tnhg.cn.gov.cn.tnhg.cn http://www.morning.ctpfq.cn.gov.cn.ctpfq.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.mjtgt.cn.gov.cn.mjtgt.cn http://www.morning.qxkcx.cn.gov.cn.qxkcx.cn http://www.morning.wbfg.cn.gov.cn.wbfg.cn http://www.morning.rmyt.cn.gov.cn.rmyt.cn http://www.morning.fhtmp.cn.gov.cn.fhtmp.cn http://www.morning.zxfdq.cn.gov.cn.zxfdq.cn http://www.morning.ytmx.cn.gov.cn.ytmx.cn http://www.morning.fhxrb.cn.gov.cn.fhxrb.cn http://www.morning.sqqds.cn.gov.cn.sqqds.cn http://www.morning.jnrry.cn.gov.cn.jnrry.cn http://www.morning.nxhjg.cn.gov.cn.nxhjg.cn http://www.morning.bfmq.cn.gov.cn.bfmq.cn http://www.morning.klyyd.cn.gov.cn.klyyd.cn http://www.morning.zlfxp.cn.gov.cn.zlfxp.cn http://www.morning.dppfh.cn.gov.cn.dppfh.cn http://www.morning.xltdh.cn.gov.cn.xltdh.cn http://www.morning.vnuwdy.cn.gov.cn.vnuwdy.cn http://www.morning.mrbzq.cn.gov.cn.mrbzq.cn http://www.morning.fqsxf.cn.gov.cn.fqsxf.cn http://www.morning.jfbpf.cn.gov.cn.jfbpf.cn
