Syntactic analysis on programming languages: A simple approach employing automata theory

摘要

Language analysis has always been a popular subject in computer science; henceforth a vast knowledge base for compiler construction is available nowadays and consequently one can devise several models that provide efficient methods to determine the acceptance of a programming language, either at a lexical, syntactic or semantic level. By evaluating and analyzing existing techniques, we have noticed that certain algorithm complexity or grammar adaptation was required to accomplish an efficient solution. Therefore here lies the motivation for the current research. We are going to present an implementation based on a lexical and syntactic analysis model seeking to fulfill the following requisites: simplicity and expressiveness, algorithm efficiency and reduced grammar adaptation. Lexical resolution was mainly supported by regular language acceptance, whereas the subsequent syntactic analysis was performed with a pushdown automaton allowing an efficient method to recognize a context free language, avoiding additional elements, such as action-goto tables, often used in bottom-up parsers. The proposed model highlights the underlying relationship between language interpretation and automata theory. Then you may encounter an interesting approach which will provide a way to go through the most basic concepts of formal language theory and how these are wielded for solving syntactic analysis problems.