Compiler Quiz: 66 T/F? | 40 MINs to Decide | 60% to Pass

Justification

A left recursion (B -> BC) prevents the grammar from meeting LL(1) criteria.

LL(1)-ing the give grammar

S -> bT

T -> Ab | Ba

A -> aS | CB

B -> bD

C -> cD

D -> ε | cD

Left factoring S and C non-terminals is easy. The B non-terminal created left recursion and ambiguity, which can be remedied by first constructing a single b and then either zero or more c. (via new non-terminal D).

Justification

The grammar is ambiguous (unclear) because there are two different ways ‘c’ could be derived from the alphabetic string. There is no ambiguous grammar that can be parsed by LL(1), SLR(1), or LR(1) because all three are incompetent in this regard. Although it is conceivable to work through comprehensive LL(1), SLR(1), and LR(1) constructs in order to show exactly where they fail, doing so is not required. As soon as we demonstrate that a language is ambiguous, we immediately know that none of LL(1), SLR(1), or LR(1) can possibly function. This is because ambiguous grammars cannot be parsed using LL(1), SLR(1), or LR(1).

Justification

Compilers don't require that input and output languages be different. We must specify several data sets before the compiler may start. Data sets and libraries are input to the compiler, which generates object code, listings, and messages. The compiler uses utility data sets during compilation.

Justification

Micro-syntax actually addresses syntax case sensitivity.

Justification

The FIRST and FOLLOW sets table confirms this answer.

Justification

The grammar in question fails LL(1) because it lacks left factorization (non-terminals S and C).

LL(1)-ing the give grammar

S -> bT

T -> Ab | Ba

A -> aS | CB

B -> bD

C -> cD

D -> ε | cD

Left factoring S and C non-terminals is easy. The B non-terminal created left recursion and ambiguity, which can be remedied by first constructing a single b and then either zero or more c. (via new non-terminal D).

Justification

SLR(1) and LALR(1) both use the LR(0) state machine. SLR uses information about FOLLOW. LALR brings together all LR(1) states that differ only in their LOOKAHEAD.

Justification

Since the above language is left recursive, it cannot be parsed using the LL(1) algorithm. Grammar that is equivalent and free from left recursion is as follows:

A -> BA’

A’ -> +BA’ | ε

B -> int B’ | (A)B’

B’ -> ∗int B’ | ε

Justification

LR(1) parsing is more powerful but harder to grasp and less convenient than LL(1) parsing.

Justification

Cross-compiler has different target and host languages. Both languages are identical in the SELF-RESIDENT compiler.

Justification

The individual tokens are:

(1)        printf

(2)        (

(3)        "Hello, Manish! \n"

(4)        )

(5)        ;

Justification

Parser stage compiles it. In the Parser step of compilation, the compiler learns the language's grammar. It finds syntax errors and turns a program without errors into internal data structures that can be read or written in another language.

Justification

To check the statement, we may easily create LR(1) and LALR(1) parsing tables.

Justification

If LR(0) appears in multiple contexts with different LOOKAHEADS, LR(1) separates it into two.

Justification

Semantic stage compiles it. Semantic analysis evaluates code clarity. It validates the source code using the syntax tree and symbol table from the previous phase. It also verifies the code's message. Semantic Analyzer checks for type mismatches, incompatible operands, function calls with the wrong arguments, undeclared variables, and other issues. Semantic Analysis: (1) Keeps type information in a symbol table or syntax tree; and (2) Checks typos.

Justification

In Java, it is not hard to parse. Note that Java uses the LALR(1) parsing method, which can't be misunderstood and is easy to understand. Also, it's much harder to parse C++ than it is to parse C. So, it's easier to parse Java than C and C than C++.

It's important to remember that both C and C++ have grammars that aren't always clear; both are inherently ambiguous.  This means that they will give us more than one possible parse, and we will have to use the context to figure out which one is correct. Then, people make the mistaken assumption that "we need to clear up ambiguities as we parse." If we insist on dealing with ambiguities while we parse, it will make our parser much more complicated and much harder to make. When we compare how the C language is parsed to how the C++ language is parsed, we find that C++ is much harder to parse.

Justification

A compiler makes a table of symbols and analyses the syntax and semantic (meaning of the code), while an interpreter usually only analyses the syntax.

Justification

The compiler front-end parses the program, not the back-end.

Justification

Humans cannot manually build LR parser.

Justification

Due to ambiguity, the grammar does not meet LL criteria (1). The string bbcca has two leftmost derivations:

S => bBa => bBCa => bbCa => bbcCa => bbcca

or

S => bBa => bBCa => bBCCa => bbCCa => bbcCa => bbcca

LL(1)-ing the give grammar

S -> bT

T -> Ab | Ba

A -> aS | CB

B -> bD

C -> cD

D -> ε | cD

S and C non-terminals can be left factored easily. Left recursion and ambiguity were caused by the B non-terminal, and both can be solved by first creating a single b and then either zero or more c. (via new non-terminal D).

Justification

Justification

It is much harder to parse C++ than it is to parse C. It's important to remember that both C and C++ have grammars that aren't always clear; both are inherently ambiguous.  This means that they will give us more than one possible parse, and we will have to use the context to figure out which one is correct. Then, people make the mistaken assumption that "we need to clear up ambiguities as we parse." If we insist on dealing with ambiguities while we parse, it will make our parser much more complicated and much harder to make. When we compare how the C language is parsed to how the C++ language is parsed, we find that C++ is much harder to parse.

Justification

Various programming languages may use compilers, interpreters, or both.

Justification

Syntax analyzers provide ASTs, while semantic analyzers produce semantic graphs (It is an AST with additional properties).

Justification

It's easy to parse in Java. Note that Java uses the easy-to-understand and hard-to-misunderstand LALR(1) parsing method. Also, parsing C++ is much harder than parsing C. So, Java is easier to parse than C, and C is easier to parse than C++.

It's important to remember that both C and C++ have grammars that aren't always clear; both are inherently ambiguous.  This means that they will give us more than one possible parse, and we will have to use the context to figure out which one is correct. Then, people make the mistaken assumption that "we need to clear up ambiguities as we parse." If we insist on dealing with ambiguities while we parse, it will make our parser much more complicated and much harder to make. When we compare how the C language is parsed to how the C++ language is parsed, we find that C++ is much harder to parse.

Justification

It is much harder to parse C++ than it is to parse C. It's important to remember that both C and C++ have grammars that aren't always clear; both are inherently ambiguous.  This means that they will give us more than one possible parse, and we will have to use the context to figure out which one is correct. Then, people make the mistaken assumption that "we need to clear up ambiguities as we parse." If we insist on dealing with ambiguities while we parse, it will make our parser much more complicated and much harder to make. When we compare how the C language is parsed to how the C++ language is parsed, we find that C++ is much harder to parse.

Justification

FIRST(X) and FOLLOW(X) contain 2 elements:

FIRST(x) = {x};

FIRST(X) = {x, a}; and

FOLLOW(X) = {y, $}.

Justification

Here is one approach to defend this.

An SLR(1) parser traces out a rightmost derivation in reverse. The two rightmost derivations of employing both grammars deriving aⁿ are:

S => Aa => Aaa => Aaaa => Aaaaa => …

or

S => aA => aaA => aaaA => aaaaA => …

In a shift/reduce parse, all reductions occur at the top of the parsing stack, hence in the first grammar, the stack never has more than two symbols. A -> Aa reduction causes this. If the parsing stack had more than two symbols, this reduction would have failed. The second grammar reduces A -> aA. This means the parsing stack will include O(n) a's and the reduced A.

Justification

A compiler creates executable code by building BINARY OBJECT FILES that can be run more than once. An interpreter, on the other hand, creates CODE directly in temporary memory that can only be run once.

Justification

(1)        Every LL(k) grammar is also a LR(k) grammar.

(2)        It is also decidable if a given LR(k) grammar is also a LL(m) grammar for some m. 

(3)        A ε-free LL(1) grammar is also a SLR(1) grammar.

(4)        A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar.

(5)        A LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1). 

(6)        LL grammars cannot have rules left recursion. Removing left recursion from a context-free grammar is always possible. However, the resulting grammar may be bigger, require more LOOKAHEAD tokens than preferred to be an LL grammar, or not be an LL grammar at all.

(7)          LL(k) grammars that are ε-free can be transformed into GNF (Greibach Normal Form) (which by definition do not have rules with left recursion) without increasing the LOOKEAHEAD tokens.

Justification

An interpreter reads a single line of the input file and converts it into executable code, while a compiler reads all of the input files before translating them.

Justification

The FORTRAN statement DOES 5 I = 1.25 does not have 5 tokens. This sentence has three tokens: <variable, "DO5I"> <assign> <number,"1.25">.

Justification

The grammar that is presented is clear and unambiguous. This is due to the fact that the production that is used at each terminal in the string can only be uniquely determined by either the terminal itself or the terminal that is directly to its right.

Justification

Semantic stage compiles it. Semantic analysis analyses code clarity. The syntax tree and symbol table from the previous phase validate the source code. It validates the code's message. Semantic Analyzer looks for type mismatches, incompatible operands, function calls with incorrect arguments, undeclared variables, and more. Semantic Analysis: (1) Stores type data in a syntax tree or symbol table; (2) Checks typos; (3) A semantic error is shown for a type mismatch if no exact type correction rules fit the operation; (4) Determines kinds and compatibility; and (5) Checks for operands.

Justification

The part of a computer that actually does work is called the Central Processing Unit (CPU for short). Its job is to do things with computer programs written in machine language and stored in the computer's main memory (also known as RAM). It does this by doing a process called the fetch-and-execute cycle over and over again. More specifically, it gets an instruction written in machine language from memory and then does what it says.

Justification

During compilation's Parsing phase, the expression 30 = x * 3 exhibits a syntactic error.

Justification

FIRST(S’) is not applicable here. The FIRST and FOLLOW sets table confirms this answer.

Justification

Scanner stage compiles it. Scanners take a string of characters (the program's source file) and generate a string of tokens that the compiler's parser can use. Lexical mistakes: These faults are found via lexical analysis. Lexical mistakes include (1) short identifiers or constants; (2) Illegal characters; and (3) Mismatched string.

Justification

Given grammar does not have left factors, and as a result, it cannot be parsed using LL(1). Left-factored grammar equivalents are as follows:

E -> int F | E G

F -> ε | + E | − E

G -> − (E) | ∗ E

Justification

The FIRST and FOLLOW sets table confirms this answer.

Justification

The FIRST and FOLLOW sets table confirms this answer.

Justification

Unlike an interpreter, a compiler can optimize input code.

Justification

The FIRST and FOLLOW sets table confirms this answer.

Justification

The compiler handles it in the Parser stage. The Parser stage of compilation teaches the compiler the target language's grammar. It finds syntax errors and converts error-free code into internal data structures that can be read or created in a different programming language.

Justification

Lexical analyzers check every source code character. Lexical analysis in computing turns characters into ‘tokens’. Lexical analyzers, often called ‘lexers’ or ‘scanners’, are computer programs that analyze ‘words’. Lexers are often standalone functions that is called by parsers or other functions.

Justification

(1)        Every LL(k) grammar is also a LR(k) grammar.

(2)        It is also decidable if a given LR(k) grammar is also a LL(m) grammar for some m. 

(3)        A ε-free LL(1) grammar is also a SLR(1) grammar.

(4)        A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar.

(5)        A LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1). 

(6)        LL grammars cannot have rules left recursion. Removing left recursion from a context-free grammar is always possible. However, the resulting grammar may be bigger, require more LOOKAHEAD tokens than preferred to be an LL grammar, or not be an LL grammar at all.

(7)          LL(k) grammars that are ε-free can be transformed into GNF (Greibach Normal Form) (which by definition do not have rules with left recursion) without increasing the LOOKEAHEAD tokens.

Justification

During compilation's Parsing step, the Tree is just a Tree. Cycles don't exist.

Justification

Compilation and interpretation are done offline and online, respectively.

Justification

Here is one approach to defend this.

FOLLOW(A) equals {a, $} in the first grammar and {$} in the second. We may remark this discrepancy. SLR(1) parsers always reduce on the FOLLOW set, therefore for the first grammar, we will always reduce A -> Aa when it gets on the parsing stack. For the second grammar, we cannot reduce until the LOOKAHEAD is $, which happens after the final terminal is relocated.

Justification

The reversed LR(1) method is called RL(1).

Justification

Both C and C++ are context-sensitive programming languages.

(1)        We start parsing C and C++ by using a very powerful pre-processor. These pre-processors were written by hand; they are not based on Regular Expressions or Context-Free Grammars.

(2)        In C and C++, LEXERS need lexical feedback to be able to tell the difference between TYPEDEF names and IDENTIFIERS. The CONTEXT-SENSITIVE LEXER needs help from the CONTEXT-FREE PARSER to figure out the difference between "manish" as an IDENTIFIER and "manish" as a TYPEDEF name.

int manish;

typedef int manish;

manish x;

The first time the name "manish" appears, it is used as an IDENTIFIER. The second and third times, it is used as a TYPEDEF name. To figure this out, we'll have to read through the TYPEDEF declarations, which is at least as hard as parsing a context-free language because types have nested parentheses. Since the PARSER and LEXER are both recursive, it doesn't make sense to say that the PARSER doesn't care about context while the LEXER does. This is because both the PARSER and the LEXER use themselves as input.

Justification

The program's lexical analysis identifies language keywords. Lexical analysis breaks source files into keywords, constants, identifiers, operators, and other simple tokens. Tokens define a language's smallest text.

(A)       ‘Keywords’ are language-defined terms with a specific meaning. ‘IF’, ‘ELSE’, ‘INT’, ‘CHAR’, ‘DO’, ‘WHILE’, ‘FOR’, ‘STRUCT’, ‘RETURN’, et cetera are C and C++ keywords.

(B)       CONSTANTS are language-recognizable literal values. NUMBERS, STRINGS, and CHARACTERS usually make up these components:

(B1)     The numbers 3.14, 5.12, and 0 are all examples of NUMBERS that can be used in expressions. Most of the time, though, negative numbers like -17 are made by adding a minus sign (-) to a number (17).

(B2)     STRINGS are pieces of text that the language can understand. In programming languages like C and C++, double quotes go around a string like "My name is Manish Kumar Jha".

(B3)     CHARACTERS are single letters. In C and C++, a character is shown by a single quote, as in ‘m’.

(C)       Identifiers are the names that a programmer has given to something. These can be VARIABLES, FUNCTIONS, CLASSES, ENUMERATIONS, and other things. Each language has its own rules about how to write these names.

(D)       The MATHEMATICAL and LOGICAL operators, as well as any other operators that the language can understand, are called OPERATORS. In general, every language has the standard operators +, -, *, and /, and many other operators are often defined as well. Some of the other variables that can be set in C and C++ are % (modulo), -- (decrement), and ++ (increment).

(E)       Other tokens are anything that doesn't fit into any of the categories above. Most of the time, they cause errors. However, depending on the compiler, things like ‘(‘ may be valid in the language even though they are not considered keywords or operators.

Justification

Scanner stage compiles it. Scanners take a string of characters (the program's source file) and generate a string of tokens that the compiler's parser can use. Lexical mistakes: These faults are found via lexical analysis. Lexical mistakes include (1) short identifiers or constants; (2) Illegal characters; and (3) Mismatched string.

Justification

Here are the FIRST and FOLLOW sets of non-terminals.

Here is the grammar's LL(1) parsing table.

Justification

The FIRST and FOLLOW sets table confirms this answer.

Justification

Compilers can provide high-level language output. Several definitions: The term "De-Compiler" refers to a program that conducts this translation from a low-level language to a higher-level language.

Justification

The FIRST and FOLLOW sets table confirms this answer.

Justification

(1)        Every LL(k) grammar is also a LR(k) grammar.

(2)        It is also decidable if a given LR(k) grammar is also a LL(m) grammar for some m. 

(3)        A ε-free LL(1) grammar is also a SLR(1) grammar.

(4)        A LL(1) grammar with symbols that have both empty and non-empty derivations is also a LALR(1) grammar.

(5)        A LL(1) grammar with symbols that have only the empty derivation may or may not be LALR(1). 

(6)        LL grammars cannot have rules left recursion. Removing left recursion from a context-free grammar is always possible. However, the resulting grammar may be bigger, require more LOOKAHEAD tokens than preferred to be an LL grammar, or not be an LL grammar at all.

(7)          LL(k) grammars that are ε-free can be transformed into GNF (Greibach Normal Form) (which by definition do not have rules with left recursion) without increasing the LOOKEAHEAD tokens.

Justification

The FIRST and FOLLOW sets table confirms this answer.

Justification

Here are two approaches to defend this.

Justification-1

FOLLOW(A) equals {a, $} in the first grammar and {$} in the second. We may remark this discrepancy. SLR(1) parsers always reduce on the FOLLOW set, therefore for the first grammar, we will always reduce A -> Aa when it gets on the parsing stack. For the second grammar, we cannot reduce until the LOOKAHEAD is $, which happens after the final terminal is relocated.

Justification-2

An SLR(1) parser traces out a rightmost derivation in reverse. The two rightmost derivations of employing both grammars deriving aⁿ are:

S => Aa => Aaa => Aaaa => Aaaaa => …

or

S => aA => aaA => aaaA => aaaaA => …

In a shift/reduce parse, all reductions occur at the top of the parsing stack, hence in the first grammar, the stack never has more than two symbols. A -> Aa reduction causes this. If the parsing stack had more than two symbols, this reduction would have failed. The second grammar reduces A -> aA. This means the parsing stack will include O(n) a's and the reduced A.

Justification

Syntax models for programming and natural languages are commonly CFGs.

Justification

Here are two approaches to defend this.

Justification-1

FOLLOW(A) equals {a, $} in the first grammar and {$} in the second. We may remark this discrepancy. SLR(1) parsers always reduce on the FOLLOW set, therefore for the first grammar, we will always reduce A -> Aa when it gets on the parsing stack. For the second grammar, we cannot reduce until the LOOKAHEAD is $, which happens after the final terminal is relocated.

Justification-2

An SLR(1) parser traces out a rightmost derivation in reverse. The two rightmost derivations of employing both grammars deriving aⁿ are:

S => Aa => Aaa => Aaaa => Aaaaa => …

or

S => aA => aaA => aaaA => aaaaA => …

In a shift/reduce parse, all reductions occur at the top of the parsing stack, hence in the first grammar, the stack never has more than two symbols. A -> Aa reduction causes this. If the parsing stack had more than two symbols, this reduction would have failed. The second grammar reduces A -> aA. This means the parsing stack will include O(n) a's and the reduced A.

Justification

In fact, EBNF (Extended Backus Normal Form) is only more expressive in the way that it is easier to use. All EBNF definitions can be turned into the same BNF definitions.

Justification

An interpreter is a sort of computer software that, according to computer science, directly executes programming language instructions without first compiling them into a machine language program.

An interpreter often uses the following ways to execute a program:

(1)        Act on source code (based on behavior of source code) after parsing.

(2)        Execute this after translating the source code into an efficient intermediate representation.

(3)        The compiler, which is part of the interpreter system, is used to store and build code that is then executed explicitly.

Compiler versus interpreter:

The main differences between compilers and interpreters are:

(1)        An interpreter turns high-level instructions into intermediate code, whereas a compiler turns them into machine language.

(2)        At a time, the interpreter reads each line of code, while the compiler reads the whole program.

(3)        The interpreter stops translating code when it finds a mistake, after fixing the issue, the program's remaining lines will finish; but the compiler lists errors as they occur.

Characteristic differences between compiler and interpreter:

(1)        Compilers take longer to evaluate and process the program than interpreters.

(2)        Compilers generate binary format or machine code. Interpreters produce intermediate code.

(3)        In the case of a compiler, the code it makes is interpreted by another program. In an interpreter, the code is run by the computer's hardware.

(4)        In a compiler, the program runs quickly, but in an interpreter, it runs slowly.

Programming differences between compiler and interpreter:

(1)        The interpreter checks keywords, while the compiler checks syntax.

(2)        The interpreter executes the program line by line, while the compilation process executes the entire program.

(3)        The interpreter checks the program while it is being edited. The compiler, on the other hand, checks the whole program at once.

Justification

Both C and C++ are context-sensitive programming languages.

(1)        We start parsing C and C++ by using a very powerful pre-processor. These pre-processors were written by hand; they are not based on Regular Expressions or Context-Free Grammars.

(2)        In C and C++, LEXERS need lexical feedback to be able to tell the difference between TYPEDEF names and IDENTIFIERS. The CONTEXT-SENSITIVE LEXER needs help from the CONTEXT-FREE PARSER to figure out the difference between "manish" as an IDENTIFIER and "manish" as a TYPEDEF name.

int manish;

typedef int manish;

manish x;

The first time the name "manish" appears, it is used as an IDENTIFIER. The second and third times, it is used as a TYPEDEF name. To figure this out, we'll have to read through the TYPEDEF declarations, which is at least as hard as parsing a context-free language because types have nested parentheses. Since the PARSER and LEXER are both recursive, it doesn't make sense to say that the PARSER doesn't care about context while the LEXER does. This is because both the PARSER and the LEXER use themselves as input.

Justification

A compiler is a program (or group of programs) that converts computer code from one programming language (the Source Language) to another (the Target Language, often having a Binary Form known as Object Code). Executable program creation is the most common reason to transform source code.