DocumentCode :
555987
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
fYear :
2011
fDate :
18-21 Sept. 2011
Firstpage :
887
Lastpage :
890
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;
fLanguage :
English
Publisher :
ieee
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
Type :
conf
Filename :
6078314
Link To Document :
بازگشت