Grammar sample question:

For a vocabulary containing the three terminal symbols "x", "y" and "z", write a grammar generating all non-empty strings in which the x's, y's, and z's appear in alphabetical order and the number of x's equals the sum of the number of y's plus the number of z's. Example sentences of the language are:
xy
xz
xxyz
xxxyyy
xxxyzz
xxxyyz

Answer:

S -> "x" S "z" | A | "x""z"
A -> "x" A "y" | "x""y"

Grammar sample question 2:

For a language containing the two terminal symbols "x" and "y", write a grammar generating all non-empty strings in which the x's and y's appear in alphabetical order and the number of x's is at least equal to the number of y's. Example sentences of the language are:
x
xy
xxy
xxxyy
xxxy
xxyy
and xyy is NOT a valid sentence.

Answer:

S -> "x" S "y" | "x"S | "x""y" | "x"

Now write a grammar for the same language but without any ordering restriction. Example of sentences of this language are:
x
yx
xy
xyxyx
yyxx
xxxyyyx
yyyxxxxy
and xyy is still NOT a valid sentence.

Answer:

S -> "x" S "y" | "y" S "x" | "x" S | S "x" | "x""y" S | S "x""y" | "y""x" S | S "y""x" | "x""y" | "y""x" | "x"

Recursive Descent Parser sample question:

Write a recursive descent parser for the following grammar which is not LL(1):
S->i * S | i + S | i

Answer:

void S() {
    if (in == "i") {
        next();
        if (in == "+" || in == "*") {
            next();
            S();
        }
        else if (in != EOF)
            error();
    }
    else
        error();
}

Code Generation Sample Question:

Consider a language that specifies arithmetic on numbers by an operator prefix notation:
S -> "*" SS | "+" SS | "-" S | number
Write a code generator for this language that generates code for a stack machine, assume that sym is the current token, and that value is the current number value that was parsed.

void S()

{

    if(sym == timesToken)

    {

        Next();

        S();

        S();

        emit("MUL");

    }

    else if(sym == plusToken)

    {

        Next();

        S();

        S();

        emit("ADD");

    }

    else if(sym == minusToken)

    {

        Next();

        S();

        emit("NEG");

    }

    else if(sym == numberToken)

    {

        Next();

        emit("LOAD " + value); //LOAD pushes the value on the stack

    }

    else

        Error();

}

In a stack machine, all operations are performed on the elements on the stack. For example, when we say "ADD", the machine internally pops two elements from the stack, adds them together and pushes the result back on the stack. Similarly, when the instruction is "NEG", the machine internally pops one element, negates it and pushes it back on the stack. So, finally when the program finishes execution, the final result is on the stack.
In this example, we need to explicitly push something on the stack only when we see a number. Here, "LOAD" is equivalent to "push".
Please also note that a stack machine doesn't have any register. Therefore, assembly instructions of a stack machine do not have any register operands and you shouldn't be worried about the registers when you generate code for a stack machine.

int S()

{

    int x, y;

    if(sym == timesToken)

    {

        Next();

        x = S();

        y = S();

        return (x * y);

    }

    else if(sym == plusToken)

    {

        Next();

        x = S();

        y = S();

        return (x + y);

    }

    else if(sym == minusToken)

    {

        Next();

        x = S();

        return (-x);

    }

    else if(sym == numberToken)

    {

        Next();

        return (sym.val); //let's assume sym.val is the integer value of the token

    }

    else

        Error();

}