Program to find leading terminals and trailing terminals of given Grammar

Download Full DOC

Hayward Education

     

For leading terminal

Algorithm:

1.  Start

2.  For each nonterminal A and terminal a do L(A,a):= false;

3.  For each production of the form A->a or A->B do

INSTALL(A,a);

4.  While STACK not empty repeat step 5& 6

5.  Pop top pair (B,a) from STACK;

6.  For each production of the form A->B do

INSTALL(A,a)

7.  Stop

Algorithm For INSTALL(A,a)

1.    Start

2.    If L(A,a) not present do step 3 and 4. 3 . Make L(A,a)=True

4 . Push (A,a) onto stack 5 . Stop

Program:

#include<conio.h>

#include<stdio.h>

char arr[18][3] ={{'E', '+', 'F'},{'E', '*', 'F'},{'E', '(', 'F'}, {'E', ')', 'F'},{'E', 'i', 'F'},{'E', '$', 'F'},

{'F', '+', 'F'},{'F', '*', 'F'},{'F', '(', 'F'},{'F', ')', 'F'},{'F', 'i', 'F'},{'F', '$', 'F'}, {'T', '+', 'F'},

{'T', '*', 'F'}, {'T', '(', 'F'},{'T', ')', 'F'},{'T', 'i', 'F'},{'T', '$', 'F'}};

char prod[6] = "EETTFF";

char res[6][3] ={ {'E', '+', 'T'}, {'T', '\0'}, {'T', '*', 'F'},  {'F', '\0'}, {'(', 'E', ')'}, {'i', '\0'}};

char stack [5][2];

int top = -1;

void install(char pro, char re) {

    int i;

    for (i = 0; i < 18; ++i) {

        if (arr[i][0] == pro && arr[i][1] == re) {

            arr[i][2] = 'T';

            break;

        }

    }

    ++top;

    stack[top][0] = pro;

    stack[top][1] = re;

}

void main() {

    int i = 0, j;

    char pro, re, pri = ' ';

    clrscr();

    for (i = 0; i < 6; ++i) {

        for (j = 0; j < 3 && res[i][j] != '\0'; ++j) {

            if (res[i][j] == '+' || res[i][j] == '*' || res[i][j] == '(' || res[i][j] == ')' || res[i][j] == 'i' || res[i][j] == '$') {

                install(prod[i], res[i][j]);

                break;

            }

        }

    }

    while (top >= 0) {

        pro = stack[top][0];

        re = stack[top][1];

        --top;

        for (i = 0; i < 6; ++i) {

            if (res[i][0] == pro && res[i][0] != prod[i]) {

                install(prod[i], re);

            }

        }

    }

    for (i = 0; i < 18; ++i) {

        printf("\n\t");

        for (j = 0; j < 3; ++j)

            printf("%c\t", arr[i][j]);

    }

    getch();

    clrscr();

    printf("\n\n");

    for (i = 0; i < 18; ++i) {

        if (pri != arr[i][0]) {

            pri = arr[i][0];

            printf("\n\t%c -> ", pri);

        }

        if (arr[i][2] == 'T')

            printf("%c ", arr[i][1]);

    }

    getch();

}

Output:

For trailing Terminal

Algorithm

1.    Start

2.    For each non terminal A and terminal a do L(A,a):=false;

3.    For each production of the form A->a(alpha) or A-> Ba(alpha) do INSTALL(A,a)

4.    While STACK not empty repeat 5 and 6

5.    Pop top pair from stack

6.    For each production of the form A-> B(alpha) do INSTALL(A,a)

7.    Stop

Algorithm For INSTALL(A,a)

1.    Start

2.    If L[A,a] not present repeat step 3 and 4

3.    Make L(A,a)=True

4.    Push (A,a) onto stack

5.    Stop

Program :

#include<conio.h>

#include<stdio.h>

char arr[18][3] ={{'E', '+', 'F'},  {'E', '*', 'F'}, {'E', '(', 'F'},    {'E', ')', 'F'},    {'E', 'i', 'F'},

    {'E', '$', 'F'},    {'F', '+', 'F'},    {'F', '*', 'F'},    {'F', '(', 'F'},    {'F', ')', 'F'},    {'F', 'i', 'F'},

    {'F', '$', 'F'},    {'T', '+', 'F'},    {'T', '*', 'F'},    {'T', '(', 'F'},    {'T', ')', 'F'},    {'T', 'i', 'F'},

    {'T', '$', 'F'},

};

char prod[6] = "EETTFF";

char res[6][3] ={    {'E', '+', 'T'},    {'T', '\0', '\0'},    {'T', '*', 'F'},    {'F', '\0', '\0'},    {'(', 'E', ')'},   {'i', '\0', '\0'},};

char stack [5][2];

int top = -1;

void install(char pro, char re) {

    int i;

    for (i = 0; i < 18; ++i) {

        if (arr[i][0] == pro && arr[i][1] == re) {

                               }

    }

    ++top;

    arr[i][2] = 'T';

    break;

    stack[top][0] = pro;

    stack[top][1] = re;

}

void main() {

    int i = 0, j;

    char pro, re, pri = ' ';

    clrscr();

    for (i = 0; i < 6; ++i) {

        for (j = 2; j >= 0; --j) {

            if (res[i][j] == '+' || res[i][j] == '*' || res[i][j] == '(' || res[i][j] == ')' || res[i][j] == 'i' || res[i][j] == '$') {

                install(prod[i], res[i][j]);

                break;

            } else if (res[i][j] == 'E' || res[i][j] == 'F' || res[i][j] == 'T') {

                if (res[i][j - 1] == '+' || res[i][j - 1] == '*' || res[i][j - 1] == '(' || res[i][j -

                        1] == ')' || res[i][j - 1] == 'i' || res[i][j - 1] == '$') {

                    install(prod[i], res[i][j - 1]);

                    break;

                }

            }

        }

    }

    while (top >= 0) {

        pro = stack[top][0];

        re = stack[top][1];

        --top;

        for (i = 0; i < 6; ++i) {

            for (j = 2; j >= 0; --j) {

                if (res[i][0] == pro && res[i][0] != prod[i]) {

                    install(prod[i], re);

                    break;

                } else if (res[i][0] != '\0') break;

            }

        }

    }

    for (i = 0; i < 18; ++i) {

        printf("\n\t");

        for (j = 0; j < 3; ++j)

            printf("%c\t", arr[i][j]);

    }

    getch(); clrscr();

    printf("\n\n");

    for (i = 0; i < 18; ++i) {

        if (pri != arr[i][0]) {

            pri = arr[i][0];

            printf("\n\t%c -> ", pri);

        }

        if (arr[i][2] == 'T')

            printf("%c ", arr[i][1]);}

    getch();}

Output: