常规的、递归的、受限的

主要观点:探讨用于描述中缀表达式的良好形式主义,介绍了不同的语法形式及其优缺点,提出递归受限正则表达式这一形式主义,旨在同时兼顾树形状的清晰性和消除歧义性,并以具体例子进行说明和讨论。
关键信息:

  • 给出了算术表达式的几种语法形式,如最初的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) + 31 + (2 + 3)
  • 在递归受限正则表达式中,通过添加不等式来限制树的集合,如E!= E '+' [E '+' E],并说明如何将节点和规则进行匹配以判断树是否符合规则。
  • 以具体的Expr的递归受限正则表达式为例,如Expr = 'number' | '(' Expr ')' | Expr '+' Expr | Expr '*' Expr等,讨论其是否有歧义及相关证明问题。
阅读 12
0 条评论