主要观点:探讨用于描述中缀表达式的良好形式主义,介绍了不同的语法形式及其优缺点,提出递归受限正则表达式这一形式主义,旨在同时兼顾树形状的清晰性和消除歧义性,并以具体例子进行说明和讨论。
关键信息:
- 给出了算术表达式的几种语法形式,如最初的
Expr = 'number' | '(' Expr ')' | Expr '+' Expr | Expr '*' Expr
,存在歧义;改进后的Expr = Factor | Expr '+' Factor
等形式虽明确了一些性质但失去了装饰性;还有解析表达式语法Exp = Sum / Product / Atom
等。 - 介绍递归受限正则表达式,包括非终结符
N
(用大写命名)、终结符T
(用引号括起来的名字)、从非终结符到N∪T
字母表上正则表达式的生成映射、从非终结符到N∪T∪{], [}
上正则表达式的限制映射,用于表示一组带标签的树,内部节点用N
标记,叶子用T
标记,且满足特定条件。 - 以
Expr = 'number' | '(' Expr ')' | Expr '+' Expr | Expr '*' Expr
等为例展示递归受限正则表达式的应用,并提出主要问题是判断其是否有歧义,一般情况下答案是否定的,至少与上下文无关文法(CFG)一样表达能力强且 CFG 的歧义性不可判定,但或许在某些合理限制下可证明无歧义。
重要细节: - 对于有歧义的语法形式,如
1 + 2 + 3
有两种解析树(1 + 2) + 3
和1 + (2 + 3)
。 - 在递归受限正则表达式中,通过添加不等式来限制树的集合,如
E!= E '+' [E '+' E]
,并说明如何将节点和规则进行匹配以判断树是否符合规则。 - 以具体的
Expr
的递归受限正则表达式为例,如Expr = 'number' | '(' Expr ')' | Expr '+' Expr | Expr '*' Expr
等,讨论其是否有歧义及相关证明问题。
**粗体** _斜体_ [链接](http://example.com) `代码` - 列表 > 引用
。你还可以使用@
来通知其他用户。