形式文法定义是
形式文法被严格地定义为四元组G=(V,T,P,S),其中V和T分别是变元和终结符的有穷集合,并且V和T没有公共元素,即V∩T=Æ。S是一个特殊变元,称为开始符号。P是生成式的有穷集合,生成式的基本形式是:a→β,这里a和β,这里a和β都是(V∪T)*中的元素,即它们都是由变元和终结符组成的符号串,但要求a至少含有一个非终结符。在形式文法定义中,生成式集合P是至关重要的。在对使用符号的惯例作某些约定后,仅仅考查生成式,就能推断出一个文法的变元、终结符和开始符号,故可以友爱过列出生成式来定义一个形式文法。
形式文法举例
举例来说,假设字母表只包含 'a' 和 'b' 两个字符,初始符号是 'S' ,我们应用下述规则:
1. S -> aSb
2. S -> ba
于是我们可以通过把 "S" 重写为 "aSb"(规则1),我们还可以继续应用这条规则把 "aSb" 重写为 "aaSbb"。这个重写的过程不断重复,直到结果中只包含字母表中的字母为止。在例子中,我们可以得到 S -> aSb -> aaSbb -> aababb 这样的结果。由文法刻画的语言包含了所有可以这样产生的字串,比如 ba, abab, aababb, aaababbb 等等。
上一篇: 公司上市有哪些优势?股票价格对上市公司有什么影响?_世界即时看
下一篇: 最后一页
所有文章、评论、信息、数据仅供参考,使用前请核实,风险自负。
Copyright 2013-2020 高陵经济网 版权所有 京ICP备2022016840号-34
联系邮箱:920 891 263@qq.com glxcb.cn All Rights Reserved