HAT*_*ZAB 1 regex grammar finite-automata context-free-grammar
我正在从Aho的编译器构造中读取有限自动机和语法,并且我长期坚持使用这种语法.我对如何描述它没有明确的认识:
考虑以下语法:
S - >(L)| a L - > L,S | 小号
请注意,括号和逗号实际上是该语言的终端,并出现在此语法接受的句子中.尝试描述该语法生成的语言.这个语法是不明确的？
我关注的是:这种语法生成的语言能否被描述为正则表达式？我对如何做到这一点很困惑.有帮助吗？
为了表明语法是模糊的,你需要能够在解析相同的字符串时构造两个不同的解析树.您的字符串将由"(",")",","和"a"组成,因为它们是语法中唯一的终结符号.
尝试以几种方式排列这4个终端符号,看看你是否能够在维基百科的示例模糊语法的精神中展示不同的成功解析.
立即左递归往往会导致某些解析器出现问题.看看"a,a,a"是否对"L→L,S | S"做了什么有趣的事......
我关注的是这个语法生成的语言,因为正则表达式可以描述......我对如何去做感到困惑
正则表达式不能完全描述语法.重写部分语法会使这一点更加明显:
注意#1和#4.L可以产生S,S可以产生(L).这意味着S可以产生(S),其可以无限制地产生((S)),(((S)))等.关键是这些括号是匹配的; 有相同数量的"("符号为")"符号.
正则表达式不能这样做.
正则表达式映射到有限自动机.有限自动机无法计算.语言L∈{w:0 n 1 n }不是常规语言.L∈ {w:(n)n },只是"("代表"0"和")"代替"1",也不是.请参阅:常规语言 - 维基百科下的第一个示例部分.(符号注释:s 1是s,s 2是ss,...,s n重复n次.)
这意味着您无法使用正则表达式来描述该语言的这一部分.这使它成为CFG,图灵机和下推自动机的领域.
| 归档时间： |
|
| 查看次数： |
785 次 |
| 最近记录： |