正则表达式与上下文无关文法

a abc a|b ab|bc a* (ab)* (a|b)(0|1)*

都是正则表达式。

1. 任一个di都是一个新的符号，它既不属于Σ，也不属于{d1,d2,d3,…,d(i-1)}
2. 任一个ri都是一个正则表达式，能够由符号表Σ以及{d1,d2,d3,…,d(i-1)}所表示

1. 终结符号（Terminals）
2. 非终结符号（Nonterminals）
3. 一个非终结符号作为开始符号
4. 一组产生式

Regular expressions and BNF are two grammatical formalisms for describing sets of strings. Regular expressions are a concise and convenient notation for describing syntax when "nesting" is not an issue. BNF is a more powerful notation that allows for the description of nested language constructs using nonterminal symbols in arbitrary recursive combinations. Thus regular expressions are appropriate for token-level syntax of programming languages, while BNF is required for the higher-level recursive syntax of expressions, statements and so on.

原文请看 http://www.cs.sfu.ca/~cameron/Teaching/D-Lib/RegExp.html

/* This file is one of the component a Context-free Grammar Parser Generator, which accept a piece of text as the input, and generates a parser for the inputted context-free grammar. Copyright (C) 2013, Junbiao Pan (Email: ) This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see 
   . */ package analyzer; import java.io.IOException; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; import abnf.Rule; import abnf.RuleName; public class RegularAnalyzer { private List 
   
     nonRegularRules = new ArrayList 
    
      (); public List 
     
       getNonRegularRules() { return nonRegularRules; } private List 
      
        regularRules = new ArrayList 
       
         (); public List 
        
          getRegularRules() { return regularRules; } private List 
         
           undefinedRules = new ArrayList 
          
            (); public List 
           
             getUndefinedRules() { return undefinedRules; } public RegularAnalyzer(List 
            
              rules) { Set 
             
               definedRuleNames = new HashSet 
              
                (); List 
               
                 observedRules = new ArrayList 
                
                  (); observedRules.addAll(rules); boolean foundRegular; do { foundRegular = false; for(int index = observedRules.size() - 1; index >= 0; index --) { Set 
                 
                   dependent = observedRules.get(index).getElements().getDependentRuleNames(); if (definedRuleNames.containsAll(dependent)) { definedRuleNames.add(observedRules.get(index).getRuleName()); regularRules.add(observedRules.get(index)); observedRules.remove(index); foundRegular = true; continue; } if (!dependent.contains(observedRules.get(index).getRuleName())) { continue; } dependent.remove(observedRules.get(index).getRuleName()); if (definedRuleNames.containsAll(dependent)) { definedRuleNames.add(observedRules.get(index).getRuleName()); nonRegularRules.add(observedRules.get(index)); observedRules.remove(index); foundRegular = true; } } } while (foundRegular); undefinedRules.addAll(observedRules); observedRules.clear(); } }