4 ms·
> the syntax for natural numbers, for which there are at least three forms No, this incorrect[0]; consider the number 102, which under the second parse rule yi
by a1369209993 7y ago
> the syntax for natural numbers, for which there are at least three forms
No, this incorrect[0]; consider the number 102, which under the second parse rule yields first the natural number 2, to which a zero is prepended, giving 02, aka... 2; prepending a 1 then produces 12, which is clearly wrong. The third rule has the same problem, nondeterministicly. Only the first rule is correct, producing 1,10,102, by successive multiplication by ten and addition of intermediate digits.
This is similar to defining subtraction with:
sum ::= term
sum ::= term '-' sum
it may happen to match the same strings, but parsing "1-2-3" as 1-(2-3) produces 2 rather than -4.
It's not clear that chop shares this problem, but personally I would much prefer:
chop 0 x = x
chop (S n) (p:q) = chop n q
0: or least, you'd need two forms other than the ones provided for "at least three" to be true
- waynesonfire 7y agothe string '02' is not the same as '2'. I'm not sure I see a problem with the syntax grammar in parsing the string '102'.
- a1369209993 7y agoAnd the string "2-3" is not the same as "-1"; that doesn't make `sum ::= term '-' sum` correct.
- waynesonfire 7y agoconcatenation is associative while subtraction is left-associative. you're getting yourself in trouble defining subtraction in that way.
- a1369209993 7y ago> concatenation is associative while subtraction is left-associative Yes, exactly my point: `sum ::= term '-' sum` is right-associative, and therefore not a correct syntax for subtraction. Similarly, place-value notation[0] is left-associative, so `nat ::= digit | digit nat`, which is right-associative, is not a valid grammer for a place-value-notation natural number. 0: well, big-endian place-value notation, which is what we're talking about here