Bottom-up Parser-I DFA Implementation
A parser or syntax analyzer is a compiler component that breaks data into smaller elements for easy translation into another language. A parser takes input in the form of a sequence of tokens or program instructions, validates sentence sequence and usually builds a data structure in the form of a parse tree or abstract syntax tree.
Syntax analyzers follow production rules defined by means of context-free grammar. The way the production rules are implemented (derivation) divides parsing into two types: top- down parsing and bottom-up parsing
This lab teaches you
- Implementation of deterministic finite automata which will be used in bottom up parser
Student should have prior knowledge regarding DFA and bottom up parser
Introduction Bottom-up Parsing
As the name suggests, bottom-up parsing starts with the input symbols and tries to construct the parse tree up to the start symbol.
Example:
Input string : a + b * c Production rules:
S → E
E → E + T
E → E * T
E → T
T → id
Let us start bottom-up parsing
a + b * c
Read the input and check if any production matches with the input:
a + b * c
T + b * c
E + b * c
E + T * c
E * c
E * T E
S
For designing bottom up parser you need to know how to implement deterministic finite automata (DFA) and simple LR. In this lab you will learn how to implement a DFA.
Deterministic Finite Automata is a finite-state machine that accepts and rejects finite strings of symbols and only produces a unique computation (or run) of the automaton for each input string.
Lab Activities:
Activity 1:
Design a Deterministic finite automata which accepts the input ‘abcc’.
Solution:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace WindowsFormsApplication1
{
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
private void Compile_Click(object sender, EventArgs e)
{
String Initial_State = “S0”;
String Final_State = “S3”;
var dict = new Dictionary<string, Dictionary<char, object>>();
dict.Add(“S0”, new Dictionary<char, object>()
{
{ ‘a’, “S1” },
{ ‘b’, “Se” },
{ ‘c’, “Se” }
});
dict.Add(“S1”, new Dictionary<char, object>()
{
{ ‘a’, “Se” },
{ ‘b’, “S2” },
{ ‘c’, “Se” }
});
dict.Add(“S2”, new Dictionary<char, object>()
{
{ ‘a’, “Se” },
{ ‘b’, “Se” },
{ ‘c’, “S3” }
});
dict.Add(“S3”, new Dictionary<char, object>()
{
{ ‘a’, “Se” },
{ ‘b’, “Se” },
{ ‘c’, “S3″ }
});
char check; String state;
string strinput = Input.Text;
char[] charinput = strinput.ToCharArray();
check = charinput[0]; state = Initial_State; int j = 0;
while(check!=’\\’ && state!=”Se”)
{
state = dict[state][check]+””; j++;
check = charinput[j];
}
if (state.Equals(Final_State))
{ Output.Text = “RESULT OKAY”; }
else
{ Output.Text = “ERROR”; }
}
}
}
Home Activities:
Activity 1:
Design a deterministic finite automaton which will accept variables of C.
Assignment:
Submit the home activity before next lab
Related Links
- Introduction to C#
- Lexical Analyzer Recognition of operators/variables
- Recognition of keywords/constants
- Lexical Analyzer Input Buffering scheme
- Symbol Table in Compiler Construction
- First set of a given grammar using Array
- Follow set of a given grammar using Array
- Bottom-up Parser-I DFA Implementation
- Bottom-up Parser-II Stack parser using SLR
- Semantic Analyzer
#Compiler Construction complete course # Compiler Construction past paper # Compiler Construction project #Computer Science all courses #University Past Paper #Programming language #Introduction to C# #Lexical Analyzer Recognition of operators/variables #Recognition of keywords/constants #Lexical Analyzer Input Buffering scheme #Symbol Table in Compiler Construction #First set of a given grammar using Array #Follow set of a given grammar using Array #Bottom-up Parser-I DFA Implementation #Bottom-up Parser-II Stack parser using SLR #Semantic Analyzer
