[编译原理]LL(1)分析法+例题学习-程序员宅基地

技术标签：笔记

一、LL(1)分析法

LL(1) 分析法又称预测分析法，是一种不带回溯的非递归自上而下分析法。

在这里插入图片描述

二、LL(1)分析器

在这里插入图片描述

三、LL(1)分析表

在这里插入图片描述

四、LL(1)文法：分析表M不含多重定义入口的文法

在这里插入图片描述

1、一个LL(1)文法所定义得语言恰好就是它的分析表所能识别的全部句子。

2、一个上下文无关文法是LL(1)文法的充要条件（判断一个文法是否是LL(1)文法）：对每一个非终结符A的任何两个不同的产生式A→α|β，有下面条件（都是避免了多重入口）成立
（1）FIRST(α) ∩ FIRST(β) = ∅：A 的每个候选是都不存在相同的首字符
（2）假若β $\stackrel{*}\Rightarrow$ ε，则有FIRST(α) ∩ FOLLOW(A) = ∅：避免了在分析表同一栏目内出现A→α 和 A→ε的情况。

五、给出算术表达式文法求某输入串的分析过程求解步骤

1、消除左递归（可利用数学中的分配律）

形如 A → Aα∣β 其中，α、β是任意的符号串且 β 不以 A 开头。这时，可将 A 的产生式改写为右递归形式： $\begin{cases} A→βA' \\ A'→αA'| ε \end{cases}$
一般的，A → A $α_{1}$ ∣A $α_{2}$ ∣…∣A $α_{m}$ ∣ $β_{1}$ ∣ $β_{2}$ ∣…∣ $β_{n}$ 有 $\begin{cases} A→\beta _{1} A'∣\beta _{2}A'∣…∣\beta _{n}A' \\ A'→α_{1} A'∣α_{2}A'∣…∣α_{m}A'∣ε \end{cases}$

消除一切左递归

在这里插入图片描述

2、消除回溯

回溯产生的原因：候选式存在公共的左因子
一般的，设文法中关于 A 的产生式为A → δ $β_{1}$ ∣δ $β_{2}$ ∣…∣δ $β_{i}$ ∣ $\gamma_{1}$ ∣…∣ $\gamma_{j}$ 那么，可以把这些产生式改写为： $\begin{cases} A→δA'∣\gamma_{1}∣... |\gamma_{j}\\ A'→\beta _1|…|\beta_i \end{cases}$

① 提取公共左因子：A → δ( $β_{1}$ ∣ $β_{2}$ ∣…∣ $β_{i}$ )∣ $\gamma_{1}$ ∣…∣ $\gamma_{j}$
② 将产生式中由 “(” 和 “)” 括起的部分以非终结符 A' 命名则得到上述结果。

3、求解文法的FIRST集和FOLLOW集（方法：https://blog.csdn.net/qq_43717303/article/details/110210180）

4、构造LL(1)分析表

首先求出每个非终结符的 FIRST 和FOLLOW 集
然后按以下四个步骤构造分析表
①对文法 G 的每个产生式 A → α执行 ② 和③ 步；
②对每个终结符 a ∈ FIRST(A)，把 A → α 加至 M[A, a]中，其中 α 为含有首字符 a 的候选式或唯一的候选式
③若ε ∈ FIRST(A)，则对任何 b ∈ FOLLOW(A) 把 A → ε 加至 M[A, b]中
④把所有无定义的 M[A，a]标“出错标志”。

5、若预测分析表 M 含有多重定义入口冲突项，则该文法不是LL(1)文法。遵从就近匹配原选定唯一候选式得到无二义的LL(1)分析表。

6、输入串分析过程：分析开始时栈底先放入一个“#”，然后再压入文法的开始符号；当分析栈中仅剩“#”，输入串指针也指向串尾的“#”时，分析成功。

符号栈	输入串	所用产生式

符号栈	当前输入符号	输入串	说明

符号栈	当前输入符号	输入串	所用产生式	说明

六、例题

算术表达式文法如下，试给出输入串 $i_{1}$ * $i_{2}$ + $i_{3}$ 的分析过程。

G[E]: E → E+T|T
	  T → T*F|F
	  F → (E)|i

解：
1、文法G[E]消除左递归得

	G'[E]: E  → TE'
		   E' → +TE'|ε
		   T  → FT'
		   T' → *FT'|ε
		   F  → (E)|i

2、求FIRST集和FOLLOW集

FIRST(E) = {(，i}
FIRST(E') = {+，ε}
FIRST(T) = {(，i}
FIRST(T') = {*，ε}
FIRST(F) = {(，i}

FOLLOW(E) = {#，)}
FOLLOW(E') = {#，)}
FOLLOW(T) = {+，#，)}
FOLLOW(T') = {+，#，)}
FOLLOW(F) = {*，+，#，)}

3、算术表达式的LL(1)分析表

	i	+	*	(	)	#
E	E → TE’			E → TE’
E’		E’ → +TE’			E’ → ε	E’ → ε
T	T → FT’			T → FT’
T’		T’ → ε	T’ → *FT’		T’ → ε	T’ → ε
F	F → i			F → (E)

4、输入串 $i_{1}$ * $i_{2}$ + $i_{3}$ 的分析过程：除第一次出现外将弹出栈顶符号 X 将M[X,x]中 A → ? 的 ? 逆序压栈简化语言为弹出 X 将 ? 逆序压栈 / 压栈

符号栈	当前输入符号	输入串	所用产生式	说明
#E		$i_{1}$ * $i_{2}$ + $i_{3}$ #		#、E先后进栈
#E’T	$i_{1}$	$i_{1}$ * $i_{2}$ + $i_{3}$ #	E → TE’	弹出栈顶符号 E，将M[E,i]中 E → TE’的TE’逆序压栈
#E’T’F	$i_{1}$	$i_{1}$ * $i_{2}$ + $i_{3}$ #	T → FT’	弹出 T，将 FT’ 逆序压栈
#E’T’i	$i_{1}$	$i_{1}$ * $i_{2}$ + $i_{3}$ #	F → i	弹出 F，将 i 压栈
#E’T’	$i_{1}$	* $i_{2}$ + $i_{3}$ #		匹配，弹出栈顶符号 i 并读出输入串的下一个输入符号 *
#E’T’F*	*	* $i_{2}$ + $i_{3}$ #	T’ → *FT’	弹出 T’，将 i 压栈 *FT’ 逆序压栈
#E’T’F	*	* $i_{2}$ + $i_{3}$ #		匹配，弹出栈顶符号 * 并读出输入串的下一个输入符号 $i_{2}$
#E’T’ i	$i_{2}$	$i_{2}$ + $i_{3}$ #	F → i	弹出 F，将 i 压栈
#E’T’	$i_{2}$	$i_{2}$ + $i_{3}$ #		匹配，弹出栈顶符号 i 并读出输入串的下一个输入符号 +
#E’	+	+ $i_{3}$ #	T’ → ε	弹出 T’，因M[T,+]中为T’ → ε，故不压栈
#E’T+	+	+ $i_{3}$ #	E’ → +TE’	弹出 E’，将 +TE’ 逆序压栈
#E’T	+	+ $i_{3}$ #		匹配，弹出栈顶符号 + 并读出输入串的下一个输入符号 $i_{3}$
#E’T’F	$i_{3}$	$i_{3}$ #	T → FT’	弹出 T，将 FT’ 逆序压栈
#E’T’i	$i_{3}$	$i_{3}$ #	F → i	弹出 F，将 i 压栈
#E’T’	$i_{3}$	$i_{3}$ #		匹配，弹出栈顶符号 $i_{3}$ 并读出输入串的下一个输入符号 #
#E’	#	#	T’ → ε	弹出 T’，因M[T,#]中为T’ → ε，故不压栈
#	#	#	E’ → ε	弹出 E’，因M[E,#]中为E’ → ε，故不压栈

分析栈中仅剩“#”，输入串指针也指向串尾的“#”，分析成功。

本文链接：https://blog.csdn.net/qq_43717303/article/details/110942613

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

一起来找：程序员必去的社区与网站-程序员宅基地

文章浏览阅读4.6k次，点赞8次，收藏62次。新书后面准备了一个附录，列出程序员经常去的技术社区、网站等，个人见识有限，做了初步整理，分享给大家，抛砖引玉。如果你自己经常去的好地方本文没有列出，欢迎在留言中写出来。我..._程序员职场进阶32讲

10 静态文本框、命令按钮和编辑框_c++ static setwindowtext-程序员宅基地

文章浏览阅读1.4k次，点赞2次，收藏2次。静态文本框、命令按钮和编辑框是Windows应用程序中最基本的控件。静态文本框是CStatic类的对象，命令按钮是CButton类的对象，编辑框是CEdit类的对象。这三个类都是从CWnd类直接派生来的，具有CWnd类的全部功能。1、静态文本框静态文本框（Static Text）是最简单的控件。它主要用来显示文本信息，不能接受用户输入，一般不需要连接变量，也不需要处理消息。静态文本框的..._c++ static setwindowtext

＜c++STL＞: map的常见用法_c++ map循环_暮色_年华的博客-程序员宅基地

文章浏览阅读244次。map底层实现：复习一波HashMap底层实现原理解析_CalvinXCui的博客-程序员宅基地包含头文件： #include<map> ！map插入元素后自动按key值大小排序（见例）目录1.定义2.遍历3.插入元素4.访问元素例1.定义map<类型1，类型2>变量名2.遍历 C++迭代器（STL迭代器）iterator详解_又帅又酷的红头发10号-程序员宅基地_*iterator//第一步：..._c++ map循环

用于可视化分层数据的Sunburst图表教程-程序员宅基地

文章浏览阅读1.1k次。FusionCharts Suite XT是全面的跨平台、跨浏览器JavaScript图表套包，其中包括FusionCharts XT、PowerCharts XT 、FusionWidgets XT、FusionMaps XT。支持 ASP、 ASP.NET、 PHP、 JSP、 ColdFusion、 Ruby on Rails、 JavaScript、甚至简单的HTML页面。它是你值得信赖的JavaScript图表解决方案，目前在全球有45万用户选择Fusioncharts来制作专业的JavaScri_sunburst图

Android各版本对应的SDK版本，及SDK版本对应JDK版本_android 6.0 sdk23 ndk 23-程序员宅基地

文章浏览阅读1w次。Android各版本对应的SDK版本，及SDK版本对应JDK版本平台版本 SDK版本版本名称Android 11.0 30 (Android 11)Android 10.0 29 (Android Q)Android 9.0 28 Pie (Android P)Android 8.1 27 Oreo(Android O)Android 8.0 26 Oreo(Android O)（奥利奥）Android 7.1..._android 6.0 sdk23 ndk 23

PDF操作工具类_jacob runtime.getruntime().exec("taskkill-程序员宅基地

文章浏览阅读315次。/** * 根据word文件绝对路径得到pdf文件路径 * * @param fileName * @return */ public static String getPdfFileName(String fileName) { if (fileName.lastIndexOf(".doc") != -1 ||..._jacob runtime.getruntime().exec("taskkill