- 1、本文档共56页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第2章 形式语言及基础知识
第2章 形式语言的基础知识 内容提要 形式语言 文法和语言 分析树 2.1 形式语言 符号和字符串 符号:抽象实体,不加以形式定义。就像几何学中的“点”。或者叫原子概念,凭直觉去体会。 字母表:有限个符号的集合。字母表一般用?记。例如,英语的字母表?={a,b,…,z,A,B,…,Z};汉语的字母表由汉字构成。 字符串:字母表中符号的有穷序列。 字符串的长度:组成该字符串的符号的个数。字符串?的长度记作|?|。 例如字符串banana的长度为6。空字符串记作?,由0个符号组成,故|?|=0。 字符串的前缀:该字符串领头的若干符号。 字符串的后缀:该字符串结尾的若干符号。 例如,字符串abc具有前缀?,a,ab和abc;其后缀有?,c,bc,abc。 若字符串的前缀(或后缀)不是字符串本身,则称之为真前缀(或真后缀)。 字符串的子串:去掉字符串的一个前缀和后缀后得到的字符串。例如,nan是banana的一个子串。 字符串的子序列:从字符串中删除0个或多个符号后得到的串(这些被删除的符号可以不相邻)。例如,baaa是banana的子序列。 字符串的运算 字符串的连接:如果x和y是字符串,那么x和y的连接xy是把y接到x后面所形成的字符串。 例如,如果x=dog,y=house,则xy=doghouse。由?的定义,显然有??=??=?。 字符串的方幂:设x是字符串,把x自身连接n次得到字符串z,即z=xxx…x,称为字符串x的n次方幂,记作z=xn。我们规定x0=?。 例如,设x=AB,则x0=?,x1=AB,x2=ABAB,x3=ABABAB。对于,n0,有xn=xxn-1=xn-1x。 字符串集合的连接:两个字符串集合A和B的连接AB={xy|x?A,y?B},即AB是满足x属于A,y属于B的所有字符串xy所组成的集合。 例如,若A={a,b},B={c,d},则AB={ac,ad,bc,bd}。另外,我们有{?}A=A{?}=A。 对任意字符串集合A,An=AAA…A,即n个A相连。A0定义为{?}。 Kleene闭包:一个固定的字母表?上所有的字符串的集合称为集合?的Kleene闭包,记作?*。根据定义,我们有?*=?0??1??2?…??n…。 正闭包:?+=?1??2??3?…??n…称为?的正闭包。显然有 ?*=?0??+ ?+=??*=?*? 形式语言 语言:给定字母表上的任意一个字符串集合,即?*的子集(?*本身也是自己的子集,所以?*也是语言)。空集?和由空字符串组成的集合{?}都是语言。 2.2 文法和语言 文法是程序语言的生成系统,而自动机则是程序语言的识别系统。用文法可以精确地定义一个语言,并依据该文法构造出识别这个语言的自动机。因此,文法对程序语言和编译程序的构造具有重要意义,如程序语言的词法可用正规文法描述,语法可用上下文无关文法描述,而语义则要借助于上下文有关文法描述。 2.2.1 基本概念 定义 文法 文法表示成四元组G=(VT, VN, S, P),其中: (1)VT为终结符号(terminal)集,是一个非空有限集,它的每个元素称为终结符号; (2)VN为非终结符(non-terminal)集,也是一个非空有限集,其每个元素称为非终结符号。 要求VT?VN=?; (3)S为一文法开始符号,也称作识别符号,是一个特殊的非终结符号,即S?VN; (4)P是产生式的非空有限集,其中每个产生式(或称规则)是一序偶(?, ?),通常写作 ??? 读作“?是?”或“?定义为?”。在此,?为产生式的左部,而?为产生式的右部,?、?是由终结符和非终结符组成的符号串, ??(VT?VN)+且至少有一个非终结符,而??(VT?VN)*。 终结符和非终结符的集合用符号V表示,即V=VT?VN。 终结符代表了语法的最小元素。 非终结符号也称语法变量,它代表语法实体或语法范畴;非终结符代表一个一定的语法概念,因此,一个非终结符是一个类、一个集合。 例如,在程序语言中,可以把变量、常数、“+”、“*”等看作是终结符,而像“算术表达式”这个非终结符则代表着一定算术表达式组成的类,如i*(i+i)、i+i+i等;也即每个非终结符代表着由一些终结符和非终结符且满足一定规则的符号串组成的集合。 产生式是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个。 P??1,P??2,…,P??n 可将这些有相同左部的产生式合并为一个,即缩写成 P??1∣?2∣…∣?n 其中,每个?i(i=1,2,…,n)称为P的一个候选式,直竖“∣”读为“或”,它与“?”一样是用来描述文法的元语言符号(即不属于?的字符)。 例2.1 文法G=(VN, VT, P, S),其中VN={S}, V
您可能关注的文档
最近下载
- 志愿者招募方案.docx VIP
- 迅达电梯7000中文电路图.pdf
- 消防工程施工合同范本XFHT001.doc VIP
- ISO-IEC 27701.2-2024(DIS) 信息安全、网络安全和隐私保护— 隐私信息信息管理体系 - 要求和指南(雷泽佳译2024).pdf VIP
- 信息安全-网络安全和隐私保护-信息安全管理体系-要求和使用指南(整合版-2024雷泽佳).docx VIP
- QYX 06.68-2015 塑料件热铆、热熔焊接技术规范.pdf VIP
- 信息安全、网络安全和隐私保护——信息安全控制风险清单(雷泽佳编制2024A0).docx VIP
- 信息安全典型风险(威胁)清单【类别、描述、后果及控制措施示例】(雷泽佳编制2024A0).docx VIP
- 信息安全风险清单之2:信息安全典型脆弱性清单——脆弱性示例、涵义、事件类别、后果和安全控制措施(雷泽佳编制2024A0).docx VIP
- 5G-R承载CTCS-3级列控数据传输研究.pdf VIP
文档评论(0)