Open Access Open Access  Restricted Access Subscription or Fee Access

Syntax Tree Construction for the Verification of Lexical Analyzer

Kamleshwari Verma, Toran Verma


A Compiler is a language translator which translates high level language to low level language, this is the task of a compiler. Removing the bugs of source program does not assure that the generated target code is completely error free because there may be bugs in compiler also. So it is more important to verify the Compiler itself. Lexical analyzer is a first phase and main part of compiler used for scanning input stream of characters and grouping into tokens. In this paper formal construction of syntax tree is described from the regular expression to verify the lexical analyzer and this is the aim of paper. If the syntax tree will be constructed successfully for the given regular expression then the lexical analyzer will be verified. Formal specifications can be rigorously validated and verified leading to the early detection of specification errors. The specification is described using Model oriented formal specification languages Vienna Development Method (VDM) because only Vienna Development Method provide support for concurrency control and also using VDM Software requirement specification can be automatically converted into computer source code.


Compiler Verification, Formal Specification, Lexical Analyzer, Regular Expression, VDM.

Full Text:



C. J. Burgess, "The Role of Formal Methods in Software Engineering Education and Industry," Technical Report, University of Bristol, UK, 1995.

K. A. Buragga, and N. A. Zafar, "Formal Parsing Analysis of Context-Free Grammar using Left Most Derivations, ICSEA, 2011.

Nazir Ahmad zafar”Automatic construction of Formal Syntax tree Based On Regular Expression” Proceedings of the World Congress on Engineering 2012 Vol II WCE 2012, July 4 - 6, 2012, London, U.K.

Fawaz Alsaade,,Nazir Ahmad Zafar” Syntax-Tree Regular Expression Based DFA Formal Construction” July-2012 /Intelligent Information Managementv.

Michael Bebenita, Florian Brandner, Manuel ahndrich “SPUR: A Trace-Based JIT Compiler for CIL” 2010 MSR-TR

Gr. Thurmair, V. Aleksić, Chr. Schwarz “Large-scale lexical analysis “ 2009/ PANACEA.

Danny Dube and Anass Kadiri “Automatic construction of parse trees for lexemes” 2006/ National Science and Engineering Research Council of Canada.

H. Beek, A. Fantechi, S. Gnesi, and F. Mazzanti, "State/Event-Based Software Model Checking," Integrated Formal Methods, Springer, vol. 2999, pp. 128-147, 2004.

J. A. Anderson, "Automata Theory with Modern Applications," Cambridge University Press, 2006.

M. v. d. Brand, A. Sellink, and C. Verhoef, "Generation of Components for Software Renovation Factories from Context-Free Grammars," CRE, pp. 144-153, 2001.

R. Pressman, “Software Engineering- A Practitioner‟s Approach”, McGraw Hill, 5th edition. 2000.

D. Andrews. Report From The BSI Panel For The Standardisatio Of VDM (ist/5/50). In VDM '88 VDM | The Way Ahead. Springer Berlin/Heidelberg, 1988.

J.M. Spivey, “The Z Notation,Reference Manual”, 2nd edition, Prentice Hall International, 1992.

Dr.(Mrs.) Arvinder Kaur, Samridhi Gulati, Sarita Singh” Analysis of Three Formal Methods-Z, B and VDM” International Journal of Engineering Research & Technology (IJERT) Vol. 1 Issue 4, June - 2012 ISSN: 2278-0181

Pascal Felber1 and Michael K. Reiter “Advanced concurrency control in Java” 2002 John Wiley & Sons, Ltd.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.