Parsing

A semi-recursive function f is a like a recursive function, except that instead of invoking itself, it invokes some other function provided as an argument to f.

The y-combinator (aka fixed-point-combinator) is a function, that for a function f, finds a fixed point for f.

We can turn a semi-recursive function f into the corresponding recursive function g, by finding a fix point for f, which we can do using the y-combinator.

http://www.reddit.com/r/langs/

https://class.coursera.org/compilers/lecture/preview by Alex Aiken

https://www.coursera.org/course/compilers

https://class.coursera.org/compilers-003/lecture/index always available!!

http://michaelrbernste.in/2014/06/10/types-are-the-truth.html

http://www.reddit.com/r/programming/comments/28gf75/i_just_finished_writing_my_first_toy_compiler_i/

https://news.ycombinator.com/item?id=8554084

http://createyourproglang.com/

Parsing timeline

http://jeffreykegler.github.io/Ocean-of-Awareness-blog/individual/2014/09/chron.html

https://news.ycombinator.com/item?id=8290681

http://www.reddit.com/r/programming/comments/2fxkr7/parsing_a_timeline/

How to build a virtual Machine

https://www.youtube.com/watch?v=OjaAToVkoTw&feature=youtu.be

http://habrahabr.ru/post/232081/ interpretator in C++

Pratt

http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/

http://www.oilshell.org/blog/2017/03/31.html

https://github.com/vinzenz/libpypa

https://speakerdeck.com/kachayev/monadic-parsing-in-python

https://habrahabr.ru/post/309242/ paring python

Formal methods (Alloy and others)

http://research.microsoft.com/en-us/um/people/lamport/tla/formal-methods-amazon.pdf

https://zvzzt.wordpress.com/2014/05/03/python-recursion-visualization-with-rcviz/

http://www.goodmath.org/blog/2014/05/04/combinator-parsing-part-1/

https://www.udacity.com/course/cs262

http://www.dimitrifourny.com/2014/04/17/write-your-first-compiler/

http://habrahabr.ru/post/150043/ C# GoldParser

http://www.infoq.com/presentations/dart-compiler Egorov

http://szelei.me/code-generator/

P = NP ? SAT

http://habrahabr.ru/post/207112/

http://habrahabr.ru/post/208774/

http://www.buildyourownlisp.com/ build your own lisp in C

http://en.wikibooks.org/wiki/Write_Yourself_a_Scheme_in_48_Hours in Haskell

http://compilers.iecc.com/crenshaw/

http://www.hokstad.com/compiler/

http://stackoverflow.com/questions/1669/learning-to-write-a-compiler/1672#1672

http://matt.might.net/articles/standalone-lexers-with-lex/

http://i.stanford.edu/~ullman/focs.html

Flex, Bison Python

http://maniagnosis.crsr.net/2013/12/flex-and-bisonmodules-updated-sort-of.html

http://www.infoq.com/articles/HIgh-Performance-Parsers-in-Java

VTD-XML, the fastest XML parser for Java

Patrick Dubroy: Parsing, Compiling, and Static Metaprogramming

https://www.youtube.com/watch?v=UqTlToUYK1E

Compiler Club

http://neuromancer.io/join-the-compiler-creation-club/

http://tech.pro/blog/1733/join-the-compiler-creation-club

https://news.ycombinator.com/item?id=6794701

Haskell Parsec

http://yannesposito.com/Scratch/en/blog/Parsec-Presentation/

http://www.antlr.org/papers/LL-star-PLDI11.pdf ANTLR explained

http://blog.functorial.com/posts/2013-10-02-Visitor-Pattern.html

http://www.talentbuddy.co/set/5238f6544af0110af382fe93

Online classes

https://class.coursera.org/compilers/class/index

https://class.stanford.edu/courses/Engineering/Compilers/Fall2014/about

http://nathansuniversity.com/

http://blog.reverberate.org/2013/09/ll-and-lr-in-context-why-parsing-tools.html

http://mortoray.com/2012/07/20/why-i-dont-use-a-parser-generator/

http://www.cs.uoregon.edu/research/summerschool/summer12/curriculum.html

http://www.youtube.com/watch?feature=player_embedded&v=RcTaweZMEzo

http://www.stanford.edu/class/cs143/

http://www.cs.washington.edu/education/courses/csep501/08wi/lectures/index.html

https://speakerdeck.com/alex/why-python-ruby-and-javascript-are-slow

http://habrahabr.ru/post/170735/

http://habrahabr.ru/post/177701/

http://www.eclipse.org/Xtext/ framework for creating of programming and domain specific languages

http://www.codeproject.com/Articles/606610/LLLPG-2cplusLoycplustrees-2cplusandplusLES-2cpluso

JavaScript

http://habrahabr.ru/post/224081/

http://habrahabr.ru/post/227241/

https://github.com/jneen/parsimmon

https://mockbrian.com/blog/2016/11/01/making-a-language/

http://creativejs.com/2013/06/the-race-for-speed-part-2-how-javascript-compilers-work/

http://zaach.github.io/jison/ parser generator

https://www.hackerschool.com/blog/21-little-lisp-interpreter List in JavaScript

https://github.com/agershun/alasql SQL in JS

https://github.com/forward/sql-parser

https://github.com/agershun/alasql/blob/version-0.0.27/SIMILAR.md

http://akgupta.ca/blog/2013/06/07/so-you-still-dont-understand-hindley-milner-part-3/

Writing programming lang in Python

https://github.com/kvalle/diy-lisp

Write parser in Python (4 posts)

http://www.ptmcg.com/files/pyparsing_talk_apug_2016May.pdf

http://www.jayconrod.com/posts/40/a-simple-interpreter-from-scratch-in-python-part-4

http://habrahabr.ru/post/206454/ russian translation

http://habrahabr.ru/post/207662/

http://seriyps.ru/blog/2013/12/05/kak-pravilno-rasparsit-access-log/

Decision tables, Production Rules

http://info.lnpu.edu.cn/website/jpkc/rjgc/ywzl/Agile%20Programming_%20Design%20to%20Accommodate%20Change.pdf

http://www.ijarcsse.com/docs/papers/Volume_3/7_July2013/V3I7-0448.pdf

Lambda calculus

"To Dissect A Mockingbird" a more intuitive and simpler explanation of Lambda Calculus. I think the visuals help a lot.

http://dkeenan.com/Lambda/

These diagrams are interesting too: http://homepages.cwi.nl/~tromp/cl/diagrams.html

There is also Bret Victor's Alligator Eggs game: http://worrydream.com/AlligatorEggs/

I know about these because I'm currently trying to learn λ-calculus by deriving and implementing functions in CoffeeScript: https://github.com/rbonvall/lambda-coffee/blob/master/lambda...

I like this talk http://www.confreaks.com/videos/1287-rubyconf2012-y-not-adve...

Jim Weirich was an excellent speaker, and this was one of his best presentations. I thought his method of building up to the purpose of combinators (not just the Y) was much better than just an explanation. He references [1] (note url change) which does something similar and is also a good read/view.

[1] - http://codon.com/programming-with-nothing

I loved that talk. I found this lecture also instructive (not as entertaining as Jim's though):https://www.youtube.com/watch?v=FWkiO-F6X5E

http://www.flyingmachinestudios.com/programming/a-taste-of-the-lambda-calculus/

http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html

http://zeroturnaround.com/rebellabs/what-is-lambda-calculus-and-why-should-you-care/

http://en.wikipedia.org/wiki/Memoization

http://www.cs.uu.nl/wiki/Techno/ProgrammingLanguageTheoryTextsOnline

Milner-Hindley

http://stackoverflow.com/questions/12532552/what-part-of-milner-hindley-do-you-not-understand

http://logitext.mit.edu/logitext.fcgi/tutorial

https://news.ycombinator.com/item?id=5606039

http://stackoverflow.com/questions/2842809/lexers-vs-parsers

http://onoffswitch.net/building-a-custom-lexer/

http://yawnt.github.com/blog/2013/02/15/on-compilers-and-interpreters/

Monoids for programmers

https://docs.google.com/presentation/d/1gsp3Ez0n5hLiQH11kiK_2I-VotXldnFaq8CJn7UMKcI/edit#slide=id.gbb1a8d7f_059

Y-combinator

http://en.wikipedia.org/wiki/Fixed-point_combinator

http://blog.nullspace.io/obvious-python-parser.html

LR parsing

http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html

{code}

# Functions that define the operators and how to evaluate them.

# This example assumes binary operators, but this is easy to extend.

ops = {

"+": (lambda a, b: a + b),

"-": (lambda a, b: a - b)

}

def eval(tokens):

stack = []

for token in tokens:

if token in ops:

arg2 = stack.pop()

arg1 = stack.pop()

result = ops[token](arg1, arg2)

stack.append(result)

else:

stack.append(int(token))

return stack.pop()

# reverse polish notation for 7 - (2+3)

print "Result:", eval("7 2 3 + -".split())

http://habrahabr.ru/post/140441/

http://habrahabr.ru/post/140339/

http://habrahabr.ru/post/140058/

http://cmcmsu.no-ip.info/2course/

http://www.parleys.com/#st=5&id=3037&sl=3

{code}

BOOK

http://avaxhome.ws/ebooks/programming_development/general/algorithms_patterns/0470500956.html

What parsers and lexers have in common:

1. They read symbols of some alphabet from their input.
2. Hint: The alphabet doesn't necessarily have to be of letters. But it has to be of symbols which are atomic for the language understood by parser/lexer.
  1. - Symbols for the lexer: ASCII characters.
    - Symbols for the parser: the particular tokens, which are terminal symbols of their grammar.
3. They analyse these symbols and try to match them with the grammar of the language they understood.
4. And here's where the real difference usually lies. See below for more.
  1. - Grammar understood by lexers: regular grammar (Chomsky's level 3).
    - Grammar understood by parsers: context-free grammar (Chomsky's level 2).
5. They attach semantics (meaning) to the language pieces they find.
  1. - Lexers attach meaning by classifying lexemes (strings of symbols from the input) as the particulartokens. E.g. All these lexemes: *, ==, <=, ^ will be classified as "operator" token by the C/C++ lexer.
    - Parsers attach meaning by classifying strings of tokens from the input (sentences) as the particularnonterminals and building the parse tree. E.g. all these token strings: [number][operator][number], [id][operator][id], [id][operator][number][operator][number] will be classified as "expression" nonterminal by the C/C++ parser.
6. They can attach some additional meaning (data) to the recognized elements. E.g. when a lexer recognizes a character sequence constituting a proper number, it can convert it to its binary value and store with the "number" token. Similarly, when a parser recognize an expression, it can compute its value and store with the "expression" node of the syntax tree.
7. They all produce on their output a proper sentences of the language they recognize.
  1. - Lexers produce tokens, which are sentences of the regular language they recognize. Each token can have an inner syntax (though level 3, not level 2), but that doesn't matter for the output data and for the one which reads them.
    - Parsers produce syntax trees, which are representations of sentences of the context-free language they recognize. Usually it's only one big tree for the whole document/source file, because the whole document/source file is a proper sentence for them. But there aren't any reasons why parser couldn't produce a series of syntax trees on its output. E.g. it could be a parser which recognizes SGML tags sticked into plain-text. So it'll tokenize the SGML document into a series of tokens: [TXT][TAG][TAG][TXT][TAG][TXT]....

As you can see, parsers and tokenizers have much in common. One parser can be a tokenizer for other parser, which reads its input tokens as symbols from its own alphabet (tokens are simply symbols of some alphabet) in the same way as sentences from one language can be alphabetic symbols of some other, higher-level language. For example, if * and - are the symbols of the alphabet M (as "Morse code symbols"), then you can build a parser which recognizes strings of these dots and lines as letters encoded in the Morse code. The sentences in the language "Morse Code" could be tokens for some other parser, for which these tokens are atomic symbols of its language (e.g. "English Words" language). And these "English Words" could be tokens (symbols of the alphabet) for some higher-level parser which understands "English Sentences" language. And all these languages differ only in the complexity of the grammar. Nothing more.

So what's all about these "Chomsky's grammar levels"? Well, Noam Chomsky classified grammars into four levels depending on their complexity:

- Level 3: Regular grammars
- They use regular expressions, that is, they can consist only of the symbols of alphabet (a,b), their concatenations (ab,aba,bbb etd.), or alternatives (e.g. a|b).
- They can be implemented as finite state automata (FSA), like NFA (Nondeterministic Finite Automaton) or better DFA (Deterministic Finite Automaton).
- Regular grammars can't handle with nested syntax, e.g. properly nested/matched parentheses (()()(()())), nested HTML/BBcode tags, nested blocks etc. It's because state automata to deal with it should have to have infinitely many states to handle infinitely many nesting levels.
- Level 2: Context-free grammars
- They can have nested, recursive, self-similar branches in their syntax trees, so they can handle with nested structures well.
- They can be implemented as state automaton with stack. This stack is used to represent the nesting level of the syntax. In practice, they're usually implemented as a top-down, recursive-descent parser which uses machine's procedure call stack to track the nesting level, and use recursively called procedures/functions for every non-terminal symbol in their syntax.
- But they can't handle with a context-sensitive syntax. E.g. when you have an expression x+3 and in one context this x could be a name of a variable, and in other context it could be a name of a function etc.
- Level 1: Context-sensitive grammars
- Level 0: Unrestricted grammars
- Also called "phase-structure grammars".

http://wry.me/misc/peval.html

http://www.strchr.com/expression_evaluator

http://en.wikipedia.org/wiki/Lexical_analysis

lexical analysis is the process of converting a sequence of characters into a sequence of tokens. A program or function which performs lexical analysis is called alexical analyzer, lexer, or scanner. A lexer often exists as a single function which is called by a parser or another function.

http://en.wikipedia.org/wiki/The_lexer_hack

http://en.wikipedia.org/wiki/Parser

http://en.wikipedia.org/wiki/Top-down_parsing

The next stage is parsing or syntactic analysis, which is checking that the tokens form an allowable expression. This is usually done with reference to a context-free grammar which recursively defines components that can make up an expression and the order in which they must appear. However, not all rules defining programming languages can be expressed by context-free grammars alone, for example type validity and proper declaration of identifiers. These rules can be formally expressed with attribute grammars.

The final phase is semantic parsing or analysis, which is working out the implications of the expression just validated and taking the appropriate action

http://en.wikipedia.org/wiki/Ebnf

http://wiki.python.org/moin/LanguageParsing

Books:

http://avaxhome.ws/ebooks/programming_development/engineering_a_compiler.html

http://avaxhome.ws/ebooks/programming_development/1461446988_Co.html - Modern Compiler Design

http://dickgrune.com/Books/PTAPG_1st_Edition/ Book

Book: Language implementation patterns. Terence Parr

http://sigpwned.com/content/stork-example-programming-language-lesson-1-tokenization

http://sigpwned.com/content/stork-example-programming-language-lesson-3-expression-evaluation

http://zserge.com/blog/cucu-part1.html

http://zserge.com/blog/cucu-part2.html

http://habrahabr.ru/post/163979/ HTML parsing