31
votes
5answers
2k views

What does “context-free” mean in the term “context-free grammar”?

Given the amount of material that tries to explain what a context-free grammar (CFG) is, I found it surprising that very few (in my sample, less than 1 in 20) give an explanation on why such grammars ...
2
votes
2answers
633 views

Convert grammar into an LL(1) grammar which recognises the same language

I have the following sample question for a compilers exam and wanted to check my solution. Convert the following grammar into an LL(1) grammar which recognises the same language: E -> E + T E ...
0
votes
0answers
351 views

Steps in converting a grammar to LL(1) Grammar

I have the following question: Convert the following grammar into an LL(1) grammar which recognises the same language (you may assume that the grammar is unambiguous). A -> int A -> int + A A ...
5
votes
3answers
320 views

Constructing a Finite State Automaton

I have an exam question that I am unsure of the answer. The question is: In organisation X valid user names have the following structure. The user name can be either the employee’s name followed ...
3
votes
1answer
245 views

Showing a grammar is ambiguous

I have the following question taken from a compilers course exam: Show that the following grammar is ambiguous. S = XcY X = a Y = b | Z Z = bW W = d | ϵ I drew the following tree: Am I correct ...
3
votes
1answer
183 views

How to support mixed grammars?

I am currently writing a grammar for a programming language (PowerBuilder) and I am also collecting documentation about parsing and compilers creation. Now I would like to add in my grammar (that ...
5
votes
1answer
283 views

Visualizing a CUP grammar

I am implementing a grammar in CUP, and it would often be helpful to see everything at a glance. This could also be useful in finding errors quickly. Are there any programs out there that will ...