代码之家  ›  专栏  ›  技术社区  ›  Zhao

困惑于将模棱两可的语法转换为明确的语法

  •  -1
  • Zhao  · 技术社区  · 11 年前

    给出了一个不明确的语法,我被要求重写语法以使其不明确。事实上,我不知道为什么给定的语法是模棱两可的,更不用说把它改写成一个明确的语法了。

    给定的语法是S->SS|a|b,我有四个选择:

    A: S -> Sa | Sb | epsilon  
    
    B: S -> SS’
       S’-> a | b  
    
    C: S -> S | S’
       S’-> a | b 
    
    D: S -> Sa | Sb. 
    

    对于每个选择,我已经知道D是不正确的,因为它根本不生成字符串,C是不正确,因为它只匹配字符串“a”和“b”。

    然而,我认为答案是A,而正确答案是B。我认为B是错误的,因为它只是反复生成S,而B不能处理空字符串。

    1. 为什么给定的语法不明确

    2. 为什么A不正确而B正确

    1 回复  |  直到 11 年前
        1
  •  0
  •   rici    11 年前

    原始语法是不明确的,因为任何至少三个字母的字符串都可能有多个最右(或最左)派生。例如:

    S -> SS -> SSS -> SSa -> Saa -> aaa
    S -> SS -> Sa  -> SSa -> Saa -> aaa
    

    粗略地说,第一个对应于解析 a(aa) 而第二个解析 (aa)a .

    所有备选方案都不正确。 A 错误匹配εwhile B 不匹配任何内容(例如 D ). 如果 B 例如,

    S  -> SS' | S'
    S' -> a | b
    

    这将是正确的。(这种语法是左联想的。)