验证语法 - Java - 语法 - 正则表达式

Question

在我开始解释之前，让我说明这不是一个“请做我的作业”问题。我会发布我的代码和假设或猜测，但是我要求你的帮助，因为我无法解决这个问题，并且发现这个问题不仅有趣，而且是学习非常有用技能的好机会。 这个练习是我大学作业任务的一部分，截止日期已经结束。为什么我要求帮忙呢？那么，老师只会提供成绩，而不是关于如何解决这个练习的实际解释（这是大学政策），直到下一个时期，下一年。我不能等那么久，我对如何解决这个问题非常感兴趣。 这是练习演讲的总结：“有一定的孤岛，他们有自己的语言，但大多数人会犯语法错误，所以他们的州长决定要求开发人员发行一些软件，观察他们的语言规则，更正了语法“。 而这些规则：

1. 以该语言的字符只有从 'G' 到 'P' 加 'A'， 'F'， 'd'， 'Q'， 'X' 的字符。
2. 从'g'到'p'的每个字符都是一个有效的句子。
3. 如果's'是一个有效的句子，那么'As'也是有效的。
4. 如果's'和't'是有效的句子，那么'Fst'，'Dst'，'Qst'和'Xst'也是有效的句子。
5. 从1到4的规则是确定正确语法的唯一有效规则。

这不是为我们很多的不够清楚，所以我们问点3和4的老师，他解释-as的'实际上不是一个有效的一句话，那只是一个示例 - 他们意思是'A'只能跟随一个小写字母，而F，D，Q和X只能跟随两个有效的小写字母。

好吧，对于很多了解正则表达式的人来说，这可能听起来不那么复杂。其实我们没有教过正则表达式，只有JUnit - 没有与它做过什么？好的，这个练习实际上是JUnit研讨会的一部分，是的，我和你一样惊讶。那么，为什么我要提出正规的表达主题？那么，老师评论说，一些学生建议他这个练习可以使用正则表达式轻松解决。

我在Java中使用NetBeans发展，我会后的代码中最重要的部分，我到目前为止有：

Pattern patronUno = Pattern.compile("[ghijklmnop]"); 
Pattern patronDos = Pattern.compile("A*[ghijklmnop]|A*"); 
Pattern patronTres = Pattern.compile("([FDQX]+([ghijklmnop]{2,2}))"); 
Pattern patronCuatro = Pattern.compile("[A][FDQX]"); 

public String validar(String sentencia){   
    Matcher coincidenciaUno = patronUno.matcher(sentencia); 
    Matcher coincidenciaDos = patronDos.matcher(sentencia); 
    Matcher coincidenciaTres = patronTres.matcher(sentencia); 
    Matcher coincidenciaCuatro = patronCuatro.matcher(sentencia); 

    if(coincidenciaUno.matches() || coincidenciaDos.matches() || 
       coincidenciaTres.matches() || coincidenciaCuatro.matches()) 
     return "YES"; 
    else 
     return "NO"; 
} 

而且我的第一个测试的情况下，我有，预先核准由教师是：

实施例在实施例OUT

• 蛋白原NO
• Xij YES
• AXij YES
• DKLM NO

现在，AXij是有效的，因为A本身是有效的，并且xij表示也是有效的，因此添加Xij到A是如添加的单个字符有效一句它。 而我的朋友，是我无法处理的练习的一部分;因为我无法学习 - 如果有一种方法 - 如何加入两个有效的句子。 你能帮我解决这方面的问题吗？

与该代码我张贴，我得到这些结果：

例如，在示例OUT

• 蛋白原NO
• Xij是
• AXij NO
• DKLM NO
• AAg是
• AA是
• 上午是
• 安培NO
• Amng NO

我不能让AXij被视为一个有效的句子，例如。但我可以成功验证Fx为无效，Xij为有效，Dklm为无效等。

在此先感谢您的帮助。我发布这个，因为我一直在通过这个网站搜索可以解释这个问题的例子，但是其中的任何一个对我来说都是足够清楚的。

Answer 1

不知道我什么都明白了，但这似乎匹配您的例子：

^[A]?((A[g-p])|([FDQX][g-p]{2}))$ 

demo

Answer 2

你所描述的语法很简单，完全明确，所以如果你不想去尽可能使用一个完全成熟的解析器生成像ANTLR或JavaCC的那么像这样一个递归方法可以做的工作：

public int consumeSentence(String str, int startOffset) { 
    char c = str.charAt(startOffset); 
    if(c >= 'g' && c <= 'p') { 
    return 1; 
    } else if(c == 'A') { 
    // A<s> 
    return 1 + consumeSentence(str, startOffset + 1); 
    } else if(c == 'F' || c == 'D' || c == 'Q' || c == 'X') { 
    // F<s><t> 
    int s1 = consumeSentence(str, startOffset + 1); // s 
    int s2 = consumeSentence(str, startOffset + 1 + s1); // t 
    return 1 + s1 + s2; 
    } else { 
    throw new IllegalArgumentException("illegal sentence"); 
    } 
} 

这尝试从给定位置开始的字符串中消费内容，直到它到达有效句子的末尾，返回消耗的字符数。要检查字符串s是否为有效句子，请致电consumeSentence(s, 0)并查看返回值是否等于原始字符串的长度。如果它返回的东西更少，或者它抛出异常，那么原始字符串不是有效的句子。

这是一种解析器生成器为您构建的逻辑，但这种情况很简单，您可以手动编写它。

Answer 3

我没有足够的理论知识来证明这是上下文无关文法。尽管已知正则表达式与上下文相关的语法相匹配，但无需递归（Perl/PCRE）或平衡组（.NET），正则表达式无法解决上下文无关的简单问题，例如括号平衡。

顺便说一句，这是语法：

S -> 'g' | 'h' | ... | 'p' 
S -> 'A' S 
S -> ('F' | 'D' | 'Q' | 'X') S S 

通常情况下，对于这种情况，最好是写一个解析器。但是，对于玩具问题，您可以使用正则表达式替换最低级别，并将叶子A[g-p]或[FDQX][g-p]{2}到g（代表有效句子）的结构减少。

public static boolean checkGrammar(String input) { 
    String prev = input; 
    while (!(input = input.replaceAll("A[g-p]|[FDQX][g-p]{2}", "g")).equals(prev)) { 
     prev = input; 
    } 

    return input.matches("[g-p]"); 
} 

Demo on ideone