• 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 » First set of a given grammar using Array

First set of a given grammar using Array

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

First set of a given grammar using Array Compiler Construction

Syntax analysis is the second phase of a compiler.The lexical analyzer works closely with the syntax analyzer. It reads character streams from the source code, checks for legal tokens, and passes the data to the syntax analyzer for further processing.

Activity Outcomes:

  • How to find the tokens/variables that are the starting symbols of a grammar

Instructor Note:

Students should know how to write grammar rules in C#

Introduction

Each time a predictive parser makes a decision, it needs to determine which production rule to apply to the leftmost non-terminal in an intermediate form, based on the next terminal (i.e. the lookahead symbol).

Take the minimalistic grammar

  1. S -> aAb
  2. A -> a | <epsilon>

and let us first parse the statement ‘aab’, so that the parser starts from looking at the (intermediate form, input) pair (‘S’,’aab’).

There is no real choice here (since ‘S’ expands in only one way), but we can still see that this is the production to choose because FIRST(S) = {a}, and arrive at the pair (‘aAb’, ‘aab’). If we started from (‘S’, ‘z’), we’d already know that there’s a syntax error, because no expansion of S begins with ‘z’ – that’s how come FIRST(S) doesn’t have a ‘z’ in it.

Moving along, (‘aAb’, ‘aab’) doesn’t begin with a non-terminal to decide a production for, so we just verify that ‘a’ matches ‘a’, which leaves us with (‘Ab’,’ab’). The nonterminal ‘A’ does have multiple ways to expand – it can either become an ‘a’, or vanish. Since FIRST(A) = {a} as well, the former choice is the right one, so we choose that, and get (‘ab’, ‘ab’). Having run out of nonterminals, the rest is just to verify that ‘a’ is in the right place to leave (‘b’,’b’), and ‘b’ matches as well, so in the end, the statement is accepted by the grammar.

This is the significance of the FIRST sets: they tell you when a nonterminal can produce the lookahead symbol as the beginning of a statement, so that it can be matched away and reduce the input. These derivations were direct, but if the grammar were

  1. S -> aDb
  2. D -> E
  3. E -> ‘a’ | <epsilon>

you would find ‘a’ in FIRST(S), FIRST(D), and FIRST(E) to drive essentially the same choices, just using one additional step of derivation.

First sets are the set of all what can begin a production rule. For example a number must begin

with a digit, a identifier must begin with a letter,…

Lab Activities:

Activity 1:

Write a program that takes at least six grammar rules. Based on these rules, find the first sets of these non-terminals.

Solution:

C Program To Find First of a Given Grammar using Array

#include<stdio.h>

#include<ctype.h>

void Find_First(char[], char);

void Array_Manipulation(char[], char);

int limit;

char production[25][25];

int main()

{

char option; char ch;

char array[25]; int count;

printf(“\nEnter Total Number of Productions:\t”);

scanf(“%d”, &limit);

for(count = 0; count < limit; count++)

{

printf(“\nValue of Production Number [%d]:\t”, count + 1);

scanf(“%s”, production[count]);

}

do

{

printf(“\nEnter a Value to Find First:\t”);

scanf(” %c”, &ch);

Find_First(array, ch);

printf(“\nFirst Value of %c:\t{ “, ch);

for(count = 0; array[count] != ‘\0’; count++)

{

printf(” %c “, array[count]);

}

printf(“}\n”);

printf(“To Continue, Press Y:\t”);

scanf(” %c”, &option);

}while(option == ‘y’ || option == ‘Y’);

return 0;

}

void Find_First(char* array, char ch)

{

int count, j, k;

char temporary_result[20];

int x;

temporary_result[0] = ‘\0’;

array[0] = ‘\0’;

if(!(isupper(ch)))

{

Array_Manipulation(array, ch);

return ;

}

for(count = 0; count < limit; count++)

{

if(production[count][0] == ch)

{

if(production[count][2] == ‘$’)

{

}

else

{

Array_Manipulation(array, ‘$’);

j = 2;

while(production[count][j] != ‘\0’)

{

x = 0;

Find_First(temporary_result, production[count][j]);

for(k = 0; temporary_result[k] != ‘\0’; k++)

{

Array_Manipulation(array,temporary_result[k]);

}

for(k = 0; temporary_result[k] != ‘\0’; k++)

{

if(temporary_result[k] == ‘$’)

{

x = 1;

break;

}

}

if(!x)

{

break;

} j++;

}

}

}

}

return;

}

void Array_Manipulation(char array[], char value)

{

int temp;

for(temp = 0; array[temp] != ‘\0’; temp++)

{

if(array[temp] == value)

{

return;

}

}

array[temp] = value; array[temp + 1] = ‘\0’;

}

Output:

Home Activities:

Activity 1:

Write a code for any given grammar that satisfy the criterion of JAVA language constructs.

Assignment:      Students must submit their home task 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

Symbol Table in Compiler Construction
November 11, 2022

Next post

Follow set of a given grammar using Array
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 …

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