The Research On Dynamic Engine Construction Technology Based On Memory Automata And Patterns

Interpretation is a vital subject for constructing software systems. A software application can be considered as an interpreter of data. For the sake of flexibility and adaptability of software systems, developers employ the interpreter to execute specific actions which can only be determined at runtime instead of development phase time and again. So, it is significant to do research on constructing interpreter with less development cost.The interpreter of a programming language is the most complex engine among all the other engines, thus this paper focus on developing the interpreter of scripting language which is used by developers extensively, and patterns of syntax and semantics are also proposed to support the construction. Key points of this thesis are SLL(*) algorithm, backtrack algorithm, LookAhead DFA tree and patterns of syntax and semantics. Through transforming the prediction of productions to states transition of automata in memory which generated from syntax, engine being developed can analyze the target as the rules defined by syntax. All the algorithms have been implemented in XD SLL(*) Parser. In order to verify the correctness, validity and other related performance of these algorithms, systematic experiment is conducted in the paper. The following are the research work has been done by the author:〔1〕Defining the regular meta-language and constructing the corresponding engineIn order to provide the lexemes for the subsequent syntax analysis, we defined a meta-language which can be used by developers to define their regular expressions in regular grammar. Based on the structure of meta-language, a recognizer has been developed which transforms the regular expressions to the equivalent syntax trees. Then the Finite State Automata is constructed in memory and conflictions in the process are solved according to the default priorities. Finally, the Finite State Automata is used to match the input stream and execute the actions which defined by developers and generate the correct outputs.〔2〕Proposing an improved SLL(*) algorithmBecause of the drawbacks of traditional SLL(*) algorithm, we proposed an improved SLL(*) algorithm which can predict the right state transition in automata more quickly. Our dynamic engine is built at runtime and all the stack information are preserved in memory, so it is convenient for prediction module to access these information and select the next correct state transition,thus avoid the explosive of paths and speed up the prediction.〔3〕Employing the SLL(*) and backtrack algorithms to guarantee completenessFor the SLL(*) algorithm cannot analyze all LL grammars, Backtrack algorithm has the ability to analyze all LL grammars including ambiguous ones, but the time costs is too high to adopt it directly and backtrack cannot guarantee the completeness by a single prediction. An approach incorporating SLL(*) algorithm and backtrack algorithm is proposed. Thus it is necessary to combine these two algorithms to accomplish the selection of next state in automata when engine is analyzing the target stream.〔4〕Implementing Structure analyzer based on Push Down Automata and mechanism executing semantic actionsStructure analyzing can be achieved through the state transition in Push Down Automata. And if semantic computation can be executed when a structure is recognized, the engine is constructed completely. Semantic computation has been classified as previous computation and post computation on syntax tree, and these two computations are used to define user's actions and to modify the default traverse order.〔5〕Analyzing and Implementing parts of grammar patterns and corresponding semantic actionsGrammar Patterns and their corresponding semantic computations are analyzed. EBNF is difficult for developers to master, so we summarize the patterns of syntax and semantics frequently appear in scripting language, and other developers can reuse these patterns directly in our class library. The patterns in class library decouples the syntax analyze module with semantic computations and improve the reusability at the same time.