一、先简单介绍一下形式语言基本知识
1、字母表:符号的非空有限集合称为字母表
2、符号串:由某一字母表中的符号组成的有限符号序列称为该字母表的符号串
二、非形式化的语言:
①语言L和M的合并,LUM={s|s∈L或 s∈M}
②语言L和M的连接,LM={st|s∈L,t∈M}
③语言L的Kleene闭包,L*=
④语言L的正闭包,L+=
解释:
前面①,②都很好理解,关于③和④,这里说明一下。
③:
集合 L 的第 i 次幂是集合 L 同自身的 i 次串接的简写。即,Li 可以被理解成由 L 中的符号形成的所有长度为 i 的字符串的集合。
L = {"ab", "c"}
L0 = {ε}
L1 = { "c"}(由L中符号形成的所有长度为1的字符串的集合)
L2 ={"ab"} ,{"cc"}(由L中符号形成的所有长度为2的字符串的集合)等等
由此,Kleene 星号应用于字符串集合的例子:
L* = {"ab", "c"}* =
={ε}∪{ "c"}∪{"ab"} ∪{"cc"}∪{"abc"} ∪{"cab"}∪{"ccc"}∪{"abcc"}∪{"abab"}∪{"cabc"}∪{ "ccab"}∪{"ababc"}∪{"abcab"}∪{"cabab"}∪{"ababab"}∪……}
={ε, "c", "ab","cc", "abc","cab", "ccc","abab", "cabc", "ccab", "abcc", "ababc", "abcab","cabab", "ababab",……}
同理,Kleene 星号应用于字符集合的例子:
{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}
④:
和③类似,只不过④中没有 L0 = {ε}
更多参见:http://zh.wikipedia.org/wiki/Kleene%E9%97%AD%E5%8C%85
三、文法(Grammar):
G={VT,VN,S,P}
VT是一个非空有限的符号集合,它的每个元素称为终结符号(Terminal)
VN是一个非空有限的符号集合,它的每个元素称为非终结符号(Non-Terminal)
S∈VN,称为文法G的开始符号
P是一个非空有限集合,它的元素称为产生式。
VT∩VN=∅
产生式,其形式为α→β,α称为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且α、β∈(VT∪VN)*,α≠ε,即α、β是由终结符和非终结符组成的符号串。
开始符S必须至少在某一产生式的左部出现一次。
另外可以对形式α→β,α→γ的产生式缩写为α→β|γ,以方便书写。
解释:
(VT∪VN) *:也就是VT∪VN的Kleene闭包
α≠ε:α不等于空符号串
用小写字母代表终结符,如:abc……,不能被拆分
用大写字母代表非终结符,如:ASBX……,可以被拆分
分享到:
相关推荐
此程序采用了加标记法 输入一个程序 得到的是压缩后的结果
编译原理LL1文法实现,使用D盘下TXT文档输入字符串例子
本程序解决了编译原理中文法的输入输出问题,识别符号是固定的,其他文法顺序自定。
编译原理实验二:压缩文法的等价变换,,zip文件里包含实验报告和源代码两部分。
东北大学编译原理课设,C语言编译器,C语言文法流程图。 东北大学编译原理课设:C语言编译器,绘制的C语言文法流程图。供学弟学妹们参考,希望对你们有所帮助。
C语言文法,在网上找到的,对学编译原理很有帮助。
编译原理2文法和形式语言 编译原理2文法和形式语言 编译原理2文法和形式语言 编译原理2文法和形式语言 编译原理2文法和形式语言
编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告——词法分析器和LL(1)文法.docx编译原理实验报告...
编译原理课程设计,LL1文法的实现。采用MFC。输入文法,分别求出每一个非终结符FIRST 集FOLLOW集和SELECT集,画出预测分析表,判定读入的文法是否是LL(1)文法,给定的任意符号串判定是否是文法中的句子,将分析过程...
大学编译原理实验用,LL1文法(C++编写)。不错的资源
AIIT 编译原理实验四LL(1)文法
编译原理-文法和语言 很详细,复习编译原理-文法和语言的同学可以重点复习一下。
LL1分析法,对于给定文法进行判断是否位LL1文法,并做相应变换使之满足LL1输出格式,对于给定的表达式和字符串输出预测分析过程 功能代码完善而全面,有图形化界面供大家参考。
自己写的编译原理实验代码,有文法压缩,文法分析,预测分析和dfa等内容,欢迎指正。
文法和语言在编译原理中的详细介绍,更加深刻的了解文法和语言在编译原理学中的详细知识
里面就一个文件夹,是写出来的源程序,里面有源代码。可以运行的。
编译原理开发设计,采用LL1文法,界面MFC设计。
编译原理LL1文法分析器C++详细源代码
正规式转化为右线性文法输出正规式转化为右线性文法输出
C++实现编译原理自动机、LL1文法、及LR(0)文法的代码