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