Title :
Checking the conformance of grammar refinements with respect to initial context-free grammars
Author :
Temprado-Battad, Bryan ; Sarasa-Cabezuelo, Antonio ; Sierra, José-Luis
Author_Institution :
Fac. de Inf., Univ. Complutense de Madrid, Madrid, Spain
Abstract :
According to this paper, to refine an initial context-free grammar supposes to devise an equivalent grammar that preserves the main syntactic structures of the initial one while making explicit other structural characteristics (e.g., associativity and priority of the operators in an expression language). Although, generally speaking, checking the equivalence of two context-free grammars is an undecidable problem, in the scenario of grammar refinement it is possible to exploit the relationships between the initial grammar and the grammar refinement to run a heuristic conformance test. These relationships must be made explicit by associating core nonterminal symbols in the initial grammar with core non-terminal symbols in the grammar refinement. Once it is made, it is possible to base the heuristic test on searching regular expressions involving both terminal and core non-terminal symbols that describe each core non-terminal symbol, and on checking the equivalence of carefully chosen pairs of such regular expressions. The paper describes the method and illustrates it with an example.
Keywords :
conformance testing; context-free grammars; decidability; core nonterminal symbols; grammar refinement conformance checking; heuristic conformance test; initial context-free grammars; syntactic structures; undecidable problem; Equations; Grammar; Information systems; Mars; Refining; Syntactics; XML;
Conference_Titel :
Computer Science and Information Systems (FedCSIS), 2011 Federated Conference on
Conference_Location :
Szczecin
Print_ISBN :
978-1-4577-0041-5
Electronic_ISBN :
978-83-60810-35-4