Scribd Logo
Upload

Welcome to Scribd!

  • 270 views

    AIM: WAP To Find Leading and Trailing of A Given Grammar.: Experiment 9

    Uploaded by

    akshat sharma
    The document describes an experiment to find the leading and trailing terminals of productions in a context-free grammar. It defines leading and trailing terminals, and provides pseudocode algorithms to compute the leading and trailing sets for each nonterminal. The algorithms use stacks and boolean arrays to iteratively determine the leading and trailing terminals by propagating this information across grammar productions. Sample C++ code is given to implement the algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    AIM: WAP To Find Leading and Trailing of A Given Grammar.: Experiment 9

    Uploaded by

    akshat sharma
    270 views8 pages
    The document describes an experiment to find the leading and trailing terminals of productions in a context-free grammar. It defines leading and trailing terminals, and provides pseudocode algorithms to compute the leading and trailing sets for each nonterminal. The algorithms use stacks and boolean arrays to iteratively determine the leading and trailing terminals by propagating this information across grammar productions. Sample C++ code is given to implement the algorithms.

    Original Title

    Lab 9 CC

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document describes an experiment to find the leading and trailing terminals of productions in a context-free grammar. It defines leading and trailing terminals, and provides pseudocode algorithms to compute the leading and trailing sets for each nonterminal. The algorithms use stacks and boolean arrays to iteratively determine the leading and trailing terminals by propagating this information across grammar productions. Sample C++ code is given to implement the algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    270 views8 pages

    AIM: WAP To Find Leading and Trailing of A Given Grammar.: Experiment 9

    Uploaded by

    akshat sharma
    The document describes an experiment to find the leading and trailing terminals of productions in a context-free grammar. It defines leading and trailing terminals, and provides pseudocode algorithms to compute the leading and trailing sets for each nonterminal. The algorithms use stacks and boolean arrays to iteratively determine the leading and trailing terminals by propagating this information across grammar productions. Sample C++ code is given to implement the algorithms.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 8

    EXPERIMENT 9:

    AIM: WAP to find leading and trailing of a given Grammar.

    THEORY:-
    LEADING

    If production is of form A → aα or A → Ba α where B is Non-terminal, and α can


    be any string, then the first terminal symbol on R.H.S is
    Leading(A) = {a}
    If production is of form A → Bα, if a is in LEADING (B), then a will also be in
    LEADING (A).

    TRAILING
    If production is of form A→ αa or A → αaB where B is Non-terminal, and α can
    be any string then,
    TRAILING (A) = {a}
    If production is of form A → αB. If a is in TRAILING (B), then a will be in
    TRAILING (A).

    Algorithm to compute LEADING


    Input − Context Free Grammar G
    Output − LEADING (A) = {a} iff Boolean Array L [A, a] = true
    Method − Procedure Install (A, a) will make L (A, a) to true if it was not true
    earlier.
    begin
    For each non-terminal A and terminal a
    L [A, a] = false ;
    For each production of form A ⟶ aα or A → B a α
    Install (A, a) ;
    While the stack not empty
    Pop top pair (B, a) form Stack ;
    For each production of form A → B α
    Install (A, a);
    end
    Procedure Install (A, a)
    begin
    If not L [A, a] then
    L [A, a] = true
    push (A, a) onto stack.
    end

    Algorithm to compute TRAILING


    Input − Context Free Grammar G
    Output − TRAILING (A) = {a} iff Boolean Array T [A, a] = true
    Method
    begin
    For each non-terminal A and terminal a
    T [A, a] = false ;
    For each production of form A ⟶ αa or A → α a B
    Install (A, a) ;
    While the stack not empty
    Pop top pair (B, a) form Stack ;
    For each production of form A → αB
    Install (A, a);
    end
    Procedure Install (A, a)
    begin
    If not T [A, a] then
    T [A, a] = true
    push (A, a) onto stack.
    end

    CODE:
    #include<iostream>
    #include<string.h>
    using namespace std;
    int nt,t,top=0;
    char s[50],NT[10],T[10],st[50],l[10][10],tr[50][50];
    int searchnt(char a)
    {
    int count=-1,i;
    for(i=0;i<nt;i++)
    {
    if(NT[i]==a)
    return i;
    }
    return count;
    }
    int searchter(char a)
    {
    int count=-1,i;
    for(i=0;i<t;i++)
    {
    if(T[i]==a)
    return i;
    }
    return count;
    }
    void push(char a)
    {
    s[top]=a;
    top++;
    }
    char pop()
    {
    top--;
    return s[top];
    }
    void installl(int a,int b)

    {
    if(l[a][b]=='f')
    {
    l[a][b]='t';
    push(T[b]);
    push(NT[a]);
    }
    }
    void installt(int a,int b)
    {
    if(tr[a][b]=='f')
    {
    tr[a][b]='t';
    push(T[b]);
    push(NT[a]);
    }
    }

    int main()
    {
    int i,s,k,j,n;
    char pr[30][30],b,c;
    cout<<"Enter the no of productions:";
    cin>>n;
    cout<<"Enter the productions one by one\n";
    for(i=0;i<n;i++)
    cin>>pr[i];
    nt=0;
    t=0;
    for(i=0;i<n;i++)
    {
    if((searchnt(pr[i][0]))==-1)
    NT[nt++]=pr[i][0];
    }
    for(i=0;i<n;i++)
    {
    for(j=3;j<strlen(pr[i]);j++)
    {
    if(searchnt(pr[i][j])==-1)
    {
    if(searchter(pr[i][j])==-1)
    T[t++]=pr[i][j];
    }
    }
    }
    for(i=0;i<nt;i++)
    {
    for(j=0;j<t;j++)
    l[i][j]='f';
    }
    for(i=0;i<nt;i++)
    {
    for(j=0;j<t;j++)

    tr[i][j]='f';
    }
    for(i=0;i<nt;i++)
    {
    for(j=0;j<n;j++)
    {
    if(NT[(searchnt(pr[j][0]))]==NT[i])
    {
    if(searchter(pr[j][3])!=-1)
    installl(searchnt(pr[j][0]),searchter(pr[j][3]));
    else
    {
    for(k=3;k<strlen(pr[j]);k++)
    {
    if(searchnt(pr[j][k])==-1)
    {
    installl(searchnt(pr[j][0]),searchter(pr[j][k]));
    break;
    }
    }
    }
    }
    }
    }
    while(top!=0)
    {
    b=pop();
    c=pop();
    for(s=0;s<n;s++)
    {
    if(pr[s][3]==b)
    installl(searchnt(pr[s][0]),searchter(c));
    }
    }
    for(i=0;i<nt;i++)
    {
    cout<<"Leading["<<NT[i]<<"]"<<"\t{";
    for(j=0;j<t;j++)
    {
    if(l[i][j]=='t')
    cout<<T[j]<<",";
    }
    cout<<"}\n";
    }

    top=0;
    for(i=0;i<nt;i++)
    {
    for(j=0;j<n;j++)
    {
    if(NT[searchnt(pr[j][0])]==NT[i])
    {
    if(searchter(pr[j][strlen(pr[j])-1])!=-1)
    installt(searchnt(pr[j][0]),searchter(pr[j][strlen(pr[j])-1]));
    else
    {
    for(k=(strlen(pr[j])-1);k>=3;k--)
    {
    if(searchnt(pr[j][k])==-1)
    {
    installt(searchnt(pr[j][0]),searchter(pr[j][k]));
    break;
    }
    }
    }
    }
    }
    }
    while(top!=0)
    {
    b=pop();
    c=pop();
    for(s=0;s<n;s++)
    {
    if(pr[s][3]==b)
    installt(searchnt(pr[s][0]),searchter(c));
    }
    }
    for(i=0;i<nt;i++)
    {
    cout<<"Trailing["<<NT[i]<<"]"<<"\t{";
    for(j=0;j<t;j++)
    {
    if(tr[i][j]=='t')
    cout<<T[j]<<",";
    }
    cout<<"}\n";
    }
    }

    OUTPUT:

    You might also like