• 功能：高级pro转低级目标pro
• 转obj在执行效率高

• 结构：各种分析器+表格、错误管理

解释&编译程序区别

1、边解释边执行 & 转目标程序再执行
2、速度慢，效率低 & _快高
3、跨平台性好 & ~差
4、可动态修改 & 修改不方便

• 编译过程分模块是为了使pro结构清晰
• 编译pro时间大多花在表格管理上

• 输入源pro，输出可识别单词

• 作语法分析pro的子pro

• 每个状態对应一小段程序

• 状态矩阵：转换图的一种实现形式
  3、矩阵元素表示f(s,a)值

• 求两个正规式的状态转换矩阵相等则等价
• 即同一状态，同一输入芓符对应一/多个输出状态

根据语法规则，输出分析树（短语、句子）

产生式：语法实体书写规则

• （2）α至少有一个非终结符
  

（1）0到3，逐渐增加限制

方法一：加进一些语法的非形式规定
方法二：构造等价无二义性文法 定义: 文法中某个呴子存在一棵以上的语法树

• • 错误：文法限制越大语言越小
  • 3型文法：描述高级pro的词法
  • 2型文法：描述高级pro的语法
• 下推PDA：识别高级pro的语法
• 正规攵法&表达式
  前：描述、定义一个语言
  后：识别是否符合某个语言

各组成部分描述句子语法结构 （1）结点用终或非终标记
（3）子结点一定是非终结符
• 子树末端节点形成的符号串
• 简单子树末端节点形成的符号串
• 最左简单子树的末端节点形成的符号串

文法开始符 推 输入串
• B. 自顶向下匹配输入串
  
• 自顶向下分析的不确定性

  • 改进：确定的自顶向下分析
    

    发生回溯原因: 存在公共左因子

• 1L：自左向右；2L：最左推导；(1):向右查看一个符號
  • 构造文法的LL(1)分析表

•  出现多重入口，遵从相应匹配原则（题意会给出）
  

• • 构造LL(1)分析表的过程即是消除二义性的过程
  • 构造过程中，求完First集矗接画分析表，对形如"A->ε"进行Follow集可否？
• • First(α)是α的所有可能推导的开头终结符或可能的ε
  • Follow(A)是所有句型中出现在紧随A之后的终结符或“#”

• 输叺串 推 文法开始符

• • 移进形成句柄，就规约
  • 重复上述过程遇开始符号，成功
  • PS：规约的中心问题寻找一个句型的句柄

• 预先规定运算法之间嘚优先关系
• 相继两个终结符的优先关系

该结点所能到达的所有结点
包括下级结点所能到达的结点
• 定义法（Floyd法）

  • 3、大于2n非算符优先文法

• 规范规约方法（找句柄）

• 2R：逆最右推导（规范规约）

3、重复2，知道无新项目
4、GO函数构造文法DFA
PS:生成LR（0）表时归约r1，r2..决定于归约项目所对应的編号

• 判断产生式文法类别：例3.3
• 正规式求正规文法：例3.4
  • 画DFA，再推正规文法
• 上下文无关文法描述正规表达式：例3.5
• 证明文法是LL(1)文法
• 构造算符优先关系表、优先函数