• About WordPress
    • WordPress.org
    • Documentation
    • Support
    • Feedback
  • Log In
  • Register
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment
Cuitutorial
  • Home
  • Courses
  • Past Paper
  • FYP
  • Interview Questions
  • University Events
  • Contact
  • Quiz & Assignment

Compiler Construction

Home » Blog » Bottom-up Parser-I DFA Implementation

Bottom-up Parser-I DFA Implementation

  • Posted by saqib
  • Categories Compiler Construction
  • Date November 11, 2022
  • Comments 1 comment

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.

DFA Implementation
DFA Implementation

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

parsing
Parsing Types

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

  • Share:
author avatar
saqib

Previous post

Follow set of a given grammar using Array
November 11, 2022

Next post

Bottom-up Parser-II Stack parser using SLR
November 11, 2022

You may also like

Compiler Construction Course Content
11 November, 2022

Compiler Construction Course Content 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 …

Semantic Analyzer
11 November, 2022

Semantic Analyzer in Compiler Construction 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 …

Bottom-up Parser-II Stack parser using SLR
11 November, 2022

Bottom-up Parser-II Stack parser using SLR in Compiler Construction 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 …

    1 Comment

Leave A Reply Cancel reply

You must be logged in to post a comment.

admin@cuitutorial.com
Facebook-f Twitter Youtube Linkedin Instagram Stack-overflow Pinterest Github Quora Whatsapp
Courses
  • All Courses
  • Past Paper
  • Final year projects
  • Interview Questions
  • Contact
Important Pages
  • Privacy Policy
  • Terms of Service
  • Cookie Policy
Links
  • University Events
  • Team
Education & learning platform for All Computer science subjects
Final year projects
Past Paper
Interview questions
Programming, C/C++, Asp.net/MVC. Android, MySql, Jquery, Ajax, javascript, Php, Html5, Bootstrap4.
NTS, GAT, PPSC, FPSC

Copyright © 2021 | Cuitutorial