- From: C. M. Sperberg-McQueen <cmsmcq@blackmesatech.com>
- Date: Tue, 17 Aug 2021 12:31:18 -0600
- To: public-ixml@w3.org
- Cc: "C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com>
I promised I would give an example of a sentence which is
infinitely ambiguous — by which I mean a sentence with an
infinite number of parse trees. Here it is:
S : ‘a’; S.
Trees include <S>a</S>, <S><S>a</S></S>, <S><S><S>a</S></S></S>, etc.
Here is another:
S: P+, ‘a’, Q+.
P: .
Q: .
The first grammar is ‘vertically’ ambiguous: arbitrary depth of nesting.
The second is ‘horizontally’ ambiguous: arbitrary numbers of empty
elements.
Michael
********************************************
C. M. Sperberg-McQueen
Black Mesa Technologies LLC
cmsmcq@blackmesatech.com
http://www.blackmesatech.com
********************************************
Received on Tuesday, 17 August 2021 18:31:38 UTC