文章基本信息

标题：Syntax-Tree Regular Expression Based DFA FormalConstruction
本地全文：下载
作者：Nazir Ahmad Zafar ; Fawaz Alsaade
期刊名称：Intelligent Information Management
印刷版ISSN：2150-8194
电子版ISSN：2150-8208
出版年度：2012
卷号：4
期号：4
页码：138-146
DOI：10.4236/iim.2012.44021
出版社：Scientific Research Publishing
摘要：Compiler is a program whose functionality is to translate a computer program written in source language into an equivalent machine code. Compiler construction is an advanced research area because of its size and complexity. The source codes are in higher level languages which are usually complex and, consequently, increase the level of abstraction. Due to such reasons, design and construction of error free compiler is a challenge of the twenty first century. Verification of a source program does not guarantee about correctness of code generated because the bugs in compiler may lead to an incorrect target program. Therefore, verification of compiler is more important than verifying the source programs. Lexical analyzer is a main phase of compiler used for scanning input and grouping into sequence of tokens. In this paper, formal construction of deterministic finite automata (DFA) based on regular expression is presented as a part of lexical analyzer. At first, syntax tree is described based on the augmented regular expression. Then formal description of important operators, checking nullability and computing first and last positions of internal nodes of the tree is described. In next, the transition diagram is described from the follow positions and converted into deterministic finite automata by defining a relationship among syntax tree, transition diagram and DFA. Formal specification of the procedure is described using Z notation and model analysis is provided using Z/Eves toolset.
关键词：Automata Theory; Compiler Verification; Lexical Analyzer; Automated Tools; Z Specification