Detect Ambiguity in a Context-Free Grammar
code-golf decision-problem grammars
Sandbox notes:
- Is the background too hard to understand? If so, should I clarify it further at the risk of making it unreasonably long, or simply delete it and state that the reader should have a knowledge of context-free grammars?
- Is there anything I should clarify in the specifications?
- Are there any other tags I should add? I couldn't find any better ones.
- Should I add more test cases?
- Apparently at the moment this problem is undecidable (which I found out way too late). Would this problem be decidable if I let solutions assume that ambiguous grammars will always have an unambiguous counterpart (in other words, the program will never be given an inherently ambiguous grammar?
Background
A Context-Free Grammar (CFG) is a set of rules for constructing strings. For example, the following is a CFG describing BF:
prog → command | command prog
command → + | - | , | . | < | > | loop
loop → [ prog ]
Let's see how the BF program ,[-] can be constructed using this grammar:
Wikipedia formally defines a grammar as a group of four items:
- A set of nonterminals, which are the "variables". In the example above, these are prog, command, and loop.
- A set of terminals, which are symbols in the alphabet that strings are composed of. In the example above, these are the BF program characters
+-,.<>[].
- A set of production rules, which define what nonterminals are allowed to become. Each rule consists of a head, which is a nonterminal, and a body, which is a list of terminals and nonterminals. In the example above, these are the production rules:
- prog → command
- prog → command prog
- command →
+
- command →
-
- ...
- command → loop
- loop →
[ prog ]
- One nonterminal that serves as the starting point for the grammar (in other words, the root node in the parse tree). In the example above, this is prog.
Consider the following context-free grammar:
bitstring → bit | bit bitstring
bit → 1 | 0
It may be tempting to collapse the two lines:
bitstring → 1 | 0 | bitstring bitstring
The disadvantage of this representation over the original is that it is ambiguous - that is, given a string, it is possible to deriving that string in multiple different ways. For example, in this grammar, the string 101 may be derived as ((10)1) or (1(01)).
The problem with ambiguity is that there is not a single way to create a representation of the generation process, which is useful for e.g. parse trees.
A useful subset of CFGs
To make CFGs easier to manipulate, we will constrain them in this way:
- Restrict the alphabet of terminals to
0 and 1,
- Identify nonterminals by a number rather than a name (either 0- or 1-indexed),
- Assume the first nonterminal (0 or 1 depending on indexing scheme) to be the initial one.
In this way, we have reduced the description of a CFG down to two inputs:
- A number representing the quantity of nonterminals
- A list of production rules, which is a list of pairs (head, body), where head designates a nonterminal for the head, and body is a list of terms which can be terminals or nonterminals.
The Task
Given a representation of a context-free grammar as described above, output a truthy or falsey value representing whether the grammar is ambiguous.
This is code-golf, so the shortest valid submission (measured in bytes wins).
Specifications
- You can use any two distinct non-empty strings instead of
1 and 0 for the terminals.
- You can assume the lists representing the bodies of the production rules are nonempty.
- You may take input in any reasonable format. If you are taking input as a number and a list and your language does not support mixed-type lists, you can assume the existence of two special nonterminals that represent the terminals
0 and 1. If this is done, please specify the two nonterminals in your answer.
You can assume that every nonterminal can "halt", that is, be mapped to a finite string of nonterminals. This means that you will never get an input like:
string → 0 string | 1 string
This also means that every nonterminal must have at least one production rule.
- Keep in mind that production rules are technically a set. The order of the rules is not relevant, so your program should be able to handle them in any order.
- You can assume there will be less than 100 production rules, and therefore less than 100 distinct nonterminals.
- You can assume that the input will be a well-formed CFG in whatever input format you designate.
Test Cases
In these examples, nonterminals are zero-indexed.
Ambiguous (Truthy)
Only empty strings:
1, [
(0, []),
(0, [0])
]
Readable form:
string →
Any string of bits:
1, [
(0, []),
(0, ["0"]),
(0, ["1"]),
(0, [0, 0])
]
Readable form:
string → 1 | 0 | string string
Nonempty strings of ones, separated by zeroes:
2, [
(1, ["1"]),
(1, ["1", 1]),
(0, [1]),
(0, [0, "0", 0])
]
Readable form:
string → ones | string 0 string
ones → 1 | 1 ones
Odd-length strings of bits:
1, [
(0, ["0"]),
(0, ["1"]),
(0, [0, 0, 0])
]
Readable form:
string → 0 | 1 | string string string
1 and 0 balanced like parenthesis:
1, [
(0, []),
(0, ["1", 0, "0"]),
(0, [0, 0])
]
Readable form:
string → 1 string 0 | string string
Unambiguous (Falsey)
Only empty strings:
1, [
(0, [])
]
Readable form:
string →
Any string of bits:
1, [
(0, []),
(0, ["0", 0]),
(0, ["1", 0])
]
Readable form:
string → 0 string | 1 string
Nonempty strings of ones, separated by zeroes:
0, [
(0, [1]),
(0, [1, "0", 0]),
(1, ["1"]),
(1, ["1", 1])
]
Readable form:
string → ones | ones 0 string
ones → 1 | 1 ones
Odd-length strings of bits:
2, [
(0, [1]),
(0, [1, 1, 0]),
(1, ["0"]),
(1, ["1"])
]
string → bit | bit bit string
bit → 0 | 1
1 and 0 balanced like parenthesis:
1, [
(0, []),
(0, ["1", 0, "0", 0])
]
Readable form:
string → 1 string 0 string
