项目作者: DavidRFerreira

项目描述 :
Implementation of an Deterministic Finite Automaton (DFA) in C to tokenize expressions for a simple Calculator (Lexical Analyser).
高级语言: C
项目地址: git://github.com/DavidRFerreira/LexicalAnalyzer_Calculator.git


lexicalAnalyzer_Calculator

Description

This is an implementation of a Lexical Analyser for expressions that we would expect from a simple calculator. For that, I implemented a deterministic finite automaton (DFA) and therefore a transition table using the C language.

I used Dev-C++ as the IDE to develop this algorithm.

Compilers and Lexical Analysers

Compilers are fundamental to modern computing. They translate human-oriented programming languages into computer-oriented machine languages.

A Lexical Analyser (or tokenizer) is the first phase in compiler designing. It takes a sequence of characters (like, for example, the code which you write on your IDE) and returns a sequence of tokens. A token is a sequence of characters which represents a unit of information in the source program.

Then, the Lexical Analyser “sends” those tokens to the Syntatic Analyser (or parser) that checks if the given input is in the correct syntax of the programming language in which the input has been written.


A Lexical Analyser for a Calculator

The Lexical Analyser implemented takes a simple mathematical expression and returns the tokens present on that same expression, making the job of a potential/possible Syntatic Analyser (parser) much easier.

Basically, this algorithm returns the tokens present in a given input expression (operator, left parentheses, right parentheses, integer or float).

Deterministic Finite Automaton (DFA) and Transitions Table Implemented


AFD




Transitions Table



Test 1 (input & output)



* input.txt *

123.43 + 123 4





**
output.txt *

———————————————————————————

INPUT EXPRESSION: 123.43 + 123 * 4



RECOGNIZED TOKENS:

Float Operator Integer Operator Integer




Test 2 (input & output)



* input.txt *

(4321 - 12.2) + dasd423

324 / 2





* output.txt *

———————————————————————————

INPUT EXPRESSION: (4321 - 12.2) + dasd423



RECOGNIZED TOKENS:

Left-Parentheses Integer Operator Float Right-Parentheses Operator Invalid Invalid Invalid Invalid Integer

———————————————————————————

INPUT EXPRESSION: 324 / 2



RECOGNIZED TOKENS:

Integer Operator Integer


Further Reading

Holub, A. (1990). Compiler Design in C. Prentice-Hall.

Fischer, C., & LeBlanc, R. (1991). Crafting a Compiler With C. Pearson.