语法树的画法(根据文法求字符串)

2023-12-25 06:20
文章标签 语法 字符串 画法 文法

本文主要是介绍语法树的画法(根据文法求字符串),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

1.语法树的画法

2.语法树的短语

3.直接短语(直接到根部)

4.素短语

5.句柄

6.算符优先分析句型


1.语法树的画法

文法G[E]:E->E+E | E*E | (E) | i ,字符串 i+i*i

推导方式有两种最左推导和最右推导(推导的技巧就是逐步靠近字符串的形式)

最左推导(从左往右替换):

E->E+E->i+E->i+E*E->i+i*E->i+i*i

最左推导得到的语法树如下:

最右推导(从右往左替换):

E->E+E->E+E*E->E+E*i->E+i*i->i+i*i

最右推导得出的语法树:

如果两种推导画出来的树相同,则说明他们有无二义性,如果树不同就是有二义性

2.语法树的短语

一个节点的最根部就是这个节点的短语,那么短语有几个呢,就看语法树中有分支的字符有几个,就有几个短语

由上图分析,第一个节点(①)的短语是i+i*i        第二个节点的短语i*i            ③④⑤的短语为i

3.直接短语(直接到根部)

所以上面这棵语法树的直接短语就是i,例如这里的直接短语就是 S,a(注意"("")"不是直接短语)

4.素短语

寻找素短语的前提是在短语中找,这些短语要满足以下条件

(1)至少包含一个终结符

(2)该短语不再包含满足第一个条件的更小的短语

由上面的语法树可以得到的语法为①i+i*i        ②i*i        ③i

①i+i*i,其中包含了满足第一个条件的②

②i*i,包含了满足第一个条件的③

所以素短语只有③

注:有些地方会提到最左素短语,最左素短语就是素短语中位于语法树最左的字符

5.句柄

最左最小的树对应的符号串,或者是直接短语中最左的符号串,在上面的语法树中,句柄就是i

例题1:

这里注意T+T也是素短语,因为他不包含满足第一个条件的短语

例题2:

消除左递归和消除回溯(这一部分比较难,还是要多做题感受下)

消除左递归:

例题1:

E-->E+T|T:

① 将T提前,其他改写为文法E':E->TE'

②剩下的写下来,"|"右边的T由于已经被提出来所以变为\varepsilon(空串):E'--->+TE'|\varepsilon

T-->T*F|F:

①T--->FT'

②*FT'|\varepsilon

F-->(E)|i:不符合左递归的形式,所以照搬即可

例题2:

消除回溯:

例题1:G[A] = A->aAB|a|b

①:将公共左因子"a"提走,另一部分改写为A',没有公共左因子的照抄:A-->aA'|b

②:将改造后的文法A'补齐:A'-->AB|\varepsilon

例题2:

6.算符优先分析句型

若有句型...N_{i}a_{i}...N_{j}a_{j}N_{j+1}....,当a_{i}...N_{j}a_{j}属于句柄时,则 N_{i} 和N_{j+1}也在句柄中,这是由于算符文法的任何句型中均无两个相邻的非终结符,且终结符和非终结符相邻时,含终结符的句柄必含相邻的非终结符,句柄终结符之间的关系如下:

例题:
 

第一步:需要将算符优先分析表得出来

这可以看:算符优先分析的方法

第二步:进行算符优先分析

①默认的#是小于当前输入符号(a)的,所以动作为移入

②接下来继续看栈顶的终结符(a),#<a且a>;所以a就形成了句柄

③对句柄进行归约

由式子可以看到:H->a|(S),可以看到句柄a可以归约为H,但是由于这里是算符优先级分析, 只考虑终结符,所以写任何非终结符是没有关系的,所以这里也可以写T

由于栈中最顶层的终结符为#,又因为#<;所以继续移进

接下来继续下一步的操作:

这里最顶层的终结符a满足,a>+,且"("< "a",所以a是这个整个语句的句柄,继续归约为T

继续下一步操作:

此时最顶层的终结符为+,因为“(”<"+",且“+” > ")",所以+为句柄,又因为,两端有两个非终结符,也在句柄中,所以由T-->T+S|S ,形似T+S,将“T+T”归约为T

由于“(“=”)“,且";" < "(" ,所以这里的"("是句柄,由于公式中含有H->G|(S),所以我们可以将其归约为H,但是这里非终结符是什么没有关系,所以统一归结为T

由于式子中包含S-->S;G|G,这里还是可以归约为S,但是同理我们归约为非终结符T也没有影响

所以可得结论:a;(a+a)G[S]文法中推出来的

但是这里我们注意:a;(a+a)的最右推导,无法推导出a;(a+a),所以a;(a+a)不是G[S]文法的句子

这与算符优先分析中的结论矛盾了,但是最右推导属于规范推导,正确答案是: (不是)

所以算符优先分析可能会错误地接受非法的句子,其推导的过程不规范。

这篇关于语法树的画法(根据文法求字符串)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/534508

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为