Lexical Analysis and Finite Automata: Key Concepts

Posted on Jan 6, 2025 in Social Anthropology

Key Characteristics of Context Sensitivity in Lex

  • (): Indicates a group.
  • (): Indicates a repetition range.
  • $: The pattern that precedes it is only recognized if it is at the end of the line.
  • ^: Outside the brackets, it indicates that the pattern is only acknowledged if it is at the beginning of the line.

Functions and Variables Provided by PCLEX

  • yylex(): Lexical analyzer.
  • yytext: This matches the current lexeme.
  • yyleng: Length of the current lexeme.
  • yylval: A global variable.
  • yyerror(): A function that is responsible for issuing and handling errors.

Finite Automata

1. Using Finite Automata

Finite automata are used to recognize languages expressed by regular expressions.

2. Another Name for Finite Automata

Finite automata are also called recognizers.

3. The Mission of a Finite Automaton

Its mission is to recognize if an input string follows the rules defined by a regular expression.

4. Deterministic Finite Automaton (DFA)

In a DFA, every transition from a state E requires a different symbol. There cannot be two transitions from the same state labeled with the same symbol.

5. Implementing an AFN

The graph appears explicitly, Input (state, symbol), Output (new state), the graph of transitions.

6. Evaluating Expressions with a Lexical Analyzer

A lexical analyzer evaluates expressions involving unsigned integer constants, relational operators, and variables.

7. Lexical Components Used by the Analyzer

Implementation with Transition Tables (TT).

8. Advantages of an AF

  • Provides applications.
  • Easy to program (trivial).
  • Shortcut.

9. Disadvantages of an AF

  • Waste of memory.

10. First Method of Implementation

Based on many identical columns/rows.

11. Second Method of Implementation

Especially useful when the transition matrix is very sparse.

12. Common Lexical Errors

  • Due to a strange character, usually appearing at the beginning of lexemes.
  • Overflow of variables/constants.
  • End of the line before closing a string.
  • Problems closing/opening remarks.

Lexical Analyzers

1. What is a Lexical Analyzer?

It is responsible for searching for words or lexical components that make up a program.

2. How Does a Lexical Analyzer Work?

It works through a sequence of characters by means of grammar.

3. Main Function of a Lexical Analyzer

Its main function is to read the input characters and produce a sequence of components as output.

4. Functions of a Lexical Analyzer

  • Remove comments.
  • Remove spaces.
  • Recognize user IDs.
  • Keep track of the lines that are read.

5. Reasons to Separate Lexical and Syntactical Analysis

It allows for the construction of specialized and more powerful processors.

6. Structure of a Lexical Graphic Processor

(Regular expression 1) (action 1)
(Regular expression 2) (action 2)
(Regular expression 3) (action 3)
(Regular expression n) (action n)

7. What is a Pattern?

It is a regular expression.

8. What is a Lexeme?

It is a specific character sequence that matches a pattern.

9. What is a Token?

A token is a terminal associated with a pattern.

10. Ways to Create a Lexical Analyzer

  • Ad hoc (bareback).
  • Finite Automata.
  • Metacompiler.