day04_编译原理学习

第四章 语法分析

自顶向下分析的概述

处理文法的编译器大致分为三种类型：通用型，自顶向下型和自底向上型。编译器中常用的方法可以分为自顶向下和自底向上。

自顶向下分析

• 从分析树的顶部（根节点）向底部（叶节点）方向构造分析树
• 可以看成是从文法开始符号S推导出词串w的过程。

• 每一步推导中，都需要做两个选择

  • 替换当前句型中的哪个非终结符
  • 用该非终结符的哪个候选式进行替换

• 基本概念：

  • 推导：从开始符号出发，每个重写步骤把一个非终结符号替换为其某个产生式的体。
  • 句型：由文法的开始符号经过零步或多步推导出的，既包含终结符号又包含非终结符号，也可能是空串。
  • 句子：不包含非终结符号的句型
  • 文法生成的语言：所有句子的集合

最左推导

• 在最左推导中，总是选择每个句型的最左非终结符进行替换。相应地，其逆过程称为最右规约。

最右推导

• 在最右推导中，总是选择每个句型的最右非终结符进行替换。相应地，其逆过程称为最左规约。

• 在自底向上的分析中，总是采用最左规约的方式，因此把最左规约称为 规范规约，而最右推导相应地称为规范推导。

最左推导和最右推导的唯一性

自顶而下的语法分析采用最左推导

• 总是采用每个句型的最左非终结符进行替换
• 根据输入流中的 下一个终结符，选择最左非终结符的一个候选式。

自顶向下语法分析的通用形式

• 递归下降分析（Recursive-Descent Parsing）

  • 由一组 过程 组成，每个过程对应一个非终结符
  • 从文法开始符号S对应的过程开始，其中递归调用文法中其它非终结符对应的过程。如果S对应的过程恰好扫描了整个输入串，则成功完成语法分析
  • 可能需要回溯，导致效率比较低

• 预测分析（Predictive Parsing）

  • 预测分析是递归下降分析的一个特例，通过在输入中向前看 固定个数（通常为1）符号来选择正确的A-产生式。
    • 可以对某些文法构造出向前看k个输入符号的预测分析器，该类文法有时也成称为LL(k)文法类
  • 预测分析不需要回溯，是一种确定的自顶向下方法

文法转换

问题一

• 同一非终结符的多个候选式存在共同前缀，将导致 回溯 现象

问题二

• 含有A->A形式产生式的文法称为是 直接左递归（immediate left recursive）的
• 如果一个文法中有一个非终结符A使得某个串a存在一个推导,那么这个文法就是左递归的。
• 经过两步或两步以上推导产生的左递归称为是 间接左递归 的

消除直接左递归

• 将左递归转换成右递归

  • 消除左递归的一般形式
    • 消除左递归是要付出代价的——引进了一些非终结符和空产生式

消除间接左递归

消除左递归算法

提取左公因子

• 通过改写产生式来 推迟决定，等读入了足够多的输入，获得足够信息后再做出正确的选择。

LL(1)文法

S_文法

• 预测分析法的工作过程
  • 从文法开始符号出发，在每一步推导过程中根据当前句型的最左非终结符A和当前输入符号a,选择正确的A-产生式。为保证分析的确定性，选出的候选式必须是唯一的。
• S_文法（简单的确定性文法）
  • 每个产生式的右部都以终结符开始
  • 同一非终结符的各个候选式的首终结符都不同
    • S_文法不含 空产生式

非终结符的后继符号集FOLLOW

• 非终结符A的后继符号集
  • 可能在某个句型的中紧跟在A后面的终结符a的集合，即为 FOLLOW(A).
    • 如果A是某个句型的最右符号，则将结束符“”添加到FOLLOW(A)中

产生式的可选集

• 产生式A->的可选集是指可以选用该产生式进行推导时对应的输入符号的集合，记为SELECT(A->)
• q_文法
  • 每个产生式的右部或为空，或以终结符开始
  • 具有相同左部的产生式有 不相交的可选集
    • q_文法不含右部以非终结符打头的产生式

串首终结符集

• 串首第一个符号，并且是终结符。简称首终结符
• 给定一个文法符号串，的串首终结符集FRIST()被定义为可以从推导的所有串首终结符构成的集合。如果，那么也在FIRST（）。

LL(1)文法

• 同一非终结符的各个产生式的 可选集互不相交
• 可以为LL(1)文法构建预测分析器.
• 解释：
  • 第一个“L”表示 从左向右扫描输入
  • 第二个“L” 表示产生 最左推导
  • “1”表示 在每一步中只需向前看 一个 输入符号来决定语法分析动作。

附：目前学习到FIRST集和FOLLOW集，难度明显上升，有些概念需要反复回味翻阅书籍才能懂，建议多看视频和书籍进行学习，下次将学习这两个集合的计算