短语、直接短语、句柄、素短语、最左素短语为句型分析的有关问题,其编译原理(第三版)书中的章节分别为2.6.3和5.3.4
概念解析:
PS:先了解文法、句型、句子等基础概念
短语:某一个句型中可以成功归约的子串,且可以使该句型规约到起始符
直接短语:只经过一步归约的短语称为直接短语
句柄:最左边的直接短语称为句柄
素短语:至少包含一个终结符且自身外不包含其他素短语的短语称为素短语
最左素短语:最左边的素短语称为最左素短语
相对于书本晦涩的概念,用最简洁明了的解释去概述这个名词是最好的方式。了解了基本的概念后,再搭配案例去了解会更加的透彻。由于是针对零基础的概念理解,因此我会把所有细节描述清楚
例题:
基础概念补充:
文法:阐明语法的工具是文法,简单说就是一套规则。
句型:从文法的识别符出发,经过若干步推导可以推导出的符号串称为该文法的句型
句子:在句型的基础上,增加约束条件,如果符号串仅由终结符组成,则称符号串为该文法的句子
F+Fi( 对应的语法树
首先找到该文法的短语,一个文法有多少非叶子节点就有多少个短语:
例题解析:
看图可知叶子此语法树的叶子节点有:F、+、F、i、(
非叶子节点从下往上按层看就是:T、T、F、V、T、V、S。总共7个所以有7个短语
因此短语为: F \qquad 相对于T F+F \qquad 相对于T F+F \qquad 相对于V F+Fi( \qquad 相对于V F+Fi( \qquad 相对于S ( \qquad 相对于F ( \qquad 相对于T
直接短语:由图可知,只经过一步规约的短语有,F
和 (
句柄:最左边的直接短语就是 F
素短语:仅包含一个终结符的短语有 F+F
和 (
最左素短语:由图可知,就是 F+F
对于这种题型最好是借助语法树这种图去直观看到该文法的句型推导过程。再去图中根据概念寻找自己的答案
我也是复习过程觉得基础很重要,老忘记一些基础概念因此特意总结一遍。如果觉得有用点个赞~