3 ms·

Thanks, this is what I'm getting at. A lot of parsing techniques seem to fall into the category of "only people who care about parsing use them." That's not t

by chubot 9y ago

Thanks, this is what I'm getting at. A lot of parsing techniques seem to fall into the category of "only people who care about parsing use them." That's not to say they will never jump the chasm. I'm just a bit conservative in my design choices and I look for algorithms that have been "battle-tested".

eesmith 9y ago
As a minor commentary, back around 2000 I used Aycock's SPARK parser for Python, which was based on the Earley algorithm. I first learned about the Earley algorithm from Aycock's presentation at the Python conference IPC7. (His use of docstrings to annotate the grammar went on to influence Beazley's PLY parser, which is LALR(1)) Aycock's work with SPARK was one of the influences of Kegler's Marpa. I was surprised to see Aycock mentioned on this timeline as it was the only name were I could say "I met him". Thus, I can say that for my work, I used the Earley algorithm. However, I don't think it was essential for the parsing I needed, only that it was available.
- chubot 9y ago
  Ah that's interesting. I recognize SPARK because it used to be part of the Python distribution, used to parse the DSL that describes Python's AST: https://eli.thegreenplace.net/2014/06/04/using-asdl-to-describe-asts-in-compilers https://eli.thegreenplace.net/2014/06/04/using-asdl-to-descr... In other words it was DSL used to implement a DSL used to implement Python -- how meta! But that post describes replacing it with a simple recursive descent parser in Python. I used ASDL itself (not SPARK) extensively in my shell: http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL But still I would say that counts as a production usage of Earley parsing! Interesting. I don't know of any others. (On the other hand, the fact that it was replaced with a few hundred lines of Python code means it probably wasn't needed in the first place.)

by chubot 9y ago

eesmith 9y ago

As a minor commentary, back around 2000 I used Aycock's SPARK parser for Python, which was based on the Earley algorithm. I first learned about the Earley algorithm from Aycock's presentation at the Python conference IPC7. (His use of docstrings to annotate the grammar went on to influence Beazley's PLY parser, which is LALR(1)) Aycock's work with SPARK was one of the influences of Kegler's Marpa. I was surprised to see Aycock mentioned on this timeline as it was the only name were I could say "I met him". Thus, I can say that for my work, I used the Earley algorithm. However, I don't think it was essential for the parsing I needed, only that it was available.

chubot 9y ago
Ah that's interesting. I recognize SPARK because it used to be part of the Python distribution, used to parse the DSL that describes Python's AST: https://eli.thegreenplace.net/2014/06/04/using-asdl-to-describe-asts-in-compilers https://eli.thegreenplace.net/2014/06/04/using-asdl-to-descr... In other words it was DSL used to implement a DSL used to implement Python -- how meta! But that post describes replacing it with a simple recursive descent parser in Python. I used ASDL itself (not SPARK) extensively in my shell: http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL http://www.oilshell.org/blog/tags.html?tag=ASDL#ASDL But still I would say that counts as a production usage of Earley parsing! Interesting. I don't know of any others. (On the other hand, the fact that it was replaced with a few hundred lines of Python code means it probably wasn't needed in the first place.)