语法分析

整章开篇

• 语法分析分为两类即自顶向下和自底向上两种。

文法和语言

• 语言：对字母表来说，^*上的任意一个子集都成为上的一个语言，记为L(L^*)。
• 句子：该语言的每一个字符串成为其的一个语句或句子。
• 文法：文法表示成四元组 G[S] = (V_T,V_N,S,)
  1. V_T是终结符集，是非空有限集，它的每个元素是终结符。
  2. V_N是非终结符集，是非空有限集，每个元素是非终结符。并且V_TV_N=
  3. S是文法开始符，是特殊的非终结符号（SV_N）
  4. 是产生式的非空有限集 产生式举例：
  5. (V_TV_N)⁺且至少有一个非终结符，不能是空串，(V_TV_N)^*
  6. 终结符不可再分，通常是一个语言的字母表，代表语法的最小元素，是一种个体记号。非终结符也称语法变量，代表一个一定的语法概念（一个类，一个集合）。文法开始符号代表语言的目标，其它语法实体只是构造语言目标的随机变量。（元语言是描述其它语言的语言，产生式右侧的表达式是产生式左侧的一个候选式，它与一样都是元语言符号（不属于的字符））
  7. 写文法的题型暂时忽略，考试有现场蒙
• 文法产生的语言：A，则称A为直接推导
• 形式语言的分类：
  1. 0型文法与0型语言（对应图灵机）
  2. 1型文法与1型语言（对应线性界限自动机，自然语言）
  3. 2型文法与2型语言（对应下推自动机，程序设计语言）
  4. 3型文法与3型语言（对应有限自动机）

推导与语法树

• 最右推导：所给句子推导队列中每一步推导都是对句型中的最右非终结符用相应产生式的右部进行替换，最左推导同理。（实在替不了先别替）最右推导是规范推导，它的逆过程是规范规约（最左规约）
• 短语：设是文法G[S]的一个句型，有SA且A，则是关于该句型的一个短语。有A则为直接短语或简单短语。两个条件缺一不可，短语属于该句型的组成部分，不能破坏句型结构的限制。
• 句柄：一个句型的最左直接短语叫句柄
• 素短语：含有终结符性质的短语，如果不存在具有相同性质的真子串，则该短语为素短语。
• 语法树：根节点是文法开始符号S，内部节点一定是非终结符，别到处瞎标，它必为叶节点且是其父节点的唯一子节点。
• 根据语法树找短语什么的：
  1. 语法树某个节点+其后代是子树（只含单层分支也就是两代节点的树叫简单子树）
  2. 短语：子树（所有）末端节点组成的符号串是子树相对于子树根的短语
  3. 直接短语：简单。。。。。。。。。。。。。。。。。
  4. 句柄：最左简单。。。。。。。。。。。。。。。。。。
  5. 素短语：子树的末端节点组成的符号串含终结符，且在该子树中不再有包含终结符的更小子树。
• 二义性：文法的一个句子能找到两种不同的最左推导或最右推导，就是二义性句子，包含该句子的文法就是二义性文法。（比如乘法优先或加法优先两种），文法二义性不代表语言二义性。不改变文法中原有的语法规则，仅加进一些语法的非形式规定。（可以加一些约束条件，比如乘法优先，并且都左结合）或构造一个等价的无二义性文法（比如加非终结符P43）。

自顶向下的语法分析

• 递归向下分析法：
  1. 含左递归以及回溯使自顶向下分析存在不确定性。
  2. 消除左递归：
     AA|
     改写：AA'
     A'A'|

例子：

IMG_20190614_203237.jpg
3. 消除回溯:(有则A'哪里产生空)
IMG_20190614_203807.jpg

• LL1分析法（预测分析法）：自左向右扫描输入串，最左推导，只向右查看一个符号就可决定如何推导

  1. 分析表的构造法：求FIRST和FOLLOW。方法如下：

     IM.jpg
     IMG_20190614_205410.jpg
     

     其实很简单：练一下就会
     比如例题3.8

     
     pra.jpg
     之后构造分析表
     new.jpg
     IMG20190614212631.jpg

  2. 分析一个输入串
     方法是：相同同消，不同规约之后反向压入栈（只是符号栈规约）
     ，两#分析成功，符号栈初始压入#和起始符号

     
     IMG_20190614_213237.jpg

自底向上语法分析

• 是一种“移进—规约”法，一旦栈顶符号形成某个句型的句柄就进行一次规约。
• 算符优先分析法：
• 算符优先文法：
  1. 首先定义一个任何产生式的右部都不含两个相继（并列）的非终结符的文法为算符文法。
  2. 定义任何两个可能相继出现的终结符a与b（它们之间最多插有一个非终结符）的优先关系。详情参考图片（后面+则G[S]是一个算符优先文法）： 14.jpg
  3. 算符优先分析表的构造
     FIRSTVT的构造：（搞P）
     如果存在产生式Pa...或PQa...
     若有产生式PQ...，则FIRSTVT(Q)FIRSTVT(P)
     LASTVT的构造：（搞P）
     如果存在产生式P...a或P...aQ
     若有产生式P...Q，则LASTVT(Q)LASTVT(P)
     循环求好几遍即可
     优先关系表的构造： 15.jpg
     例题尝试：
     sf.jpg
     分析过程
     sffx.jpg
• 优先函数

  1. 关系图法构造优先函数（Bell方法）

     
     关系图.jpg

规范归约的自底向上语法分析方法

LR分析法是自左向右自底向上规约
记住历史：
展望未来：

• LR0分析器
  活前缀：（字的前缀指字的首部，比如字abc前缀有，a，ab，abc。活前缀就是规范巨型的一个前缀，不含句柄之后任何符号。
• 圆点在最右端是规约项目，文法开始符号的规约项目是接受项目，不再最右端是待约项目。
• 为了使接受状态易于识别，将文法进行拓广。S'S是唯一的接受态。
• 构造LR0分析表的过程：
  1. 拓广文法
  2. 列出LR0的所有项目。
  3. 构造项目集规范族。先以起始符号开写，之后顺势写，一项一项移（会）。
  4. 构造dfa
  5. 构造分析表：首先看I_i的发出I_k箭头为终结符，action表I行终结符列填S_k，非终结符则是goto填k，I_i中含规约项目，将产生式标记的序号r_j全填入action第i行，含接受项目在action子表终结符“#”列栏填入acc。
  6. 练习： lr0.jpg
• SLR(1)分析
  1. 先找出dfa
  2. 找出规约项目（包括接受项目）
  3. 求FOLLOW集：如果Aa属于I_k且由I_k发出的标记为a的有向边落在I_j上，置ACTION[k,a]为Sj，若待约项目AB。。。。。。（同上），GOTO置为j，规约项目属于I_k则仅当aFOLLOW(A)时，ACTION[k,a]为ri，ACTION有移进规约冲突项目，都填，goto无此情况。
  4. 移进的FIRSTb和规约的F O L L O W（S）交集为空则不产生冲突。（与lr0区别就是r不都填，就填follow）
  5. 练习暂时忽略（因为可能不考）