Menu
I saw http://matt.might.net/teaching/compilers/spring-2015/ saying Python 3.4 is LL(1)
Is Python 3.5's grammar still LL(1) so one can write a recursive descent parser?
923
The python grammar - as most others - is given in BNF or Backus–Naur Form. Try reading up on how to read it but the basic structure is: <something> ::= (<something defined elsewhere> | [some fixed things]) [...]
In the name LL(1), the first L stands for scanning the input from left to right, the second L stands for producing a leftmost derivation, and the 1 stands for using one input symbol of lookahead at each step to make parsing action decision.
As the generated C parser is the one used by Python, this means that if something goes wrong when adding some new rules to the grammar you cannot correctly compile and execute Python anymore.
Yes. This is a deliberate language feature, and not just something that happened to be the case. PEP 3099 explicitly rejected any changes to this for the Python 2 -> 3 transition (a notably bigger transition than any 3.x -> 3.y will be):
The parser won't be more complex than LL(1).
Simple is better than complex. This idea extends to the parser. Restricting Python's grammar to an LL(1) parser is a blessing, not a curse. It puts us in handcuffs that prevent us from going overboard and ending up with funky grammar rules like some other dynamic languages that will go unnamed, such as Perl.
152
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
