| > In classic computer science, the parser of a context-free grammar usually has a minimal (boolean) output: it just either accepts or rejects the input. All of the literature I remember from my uni days on formal grammers had a recogniser defined as something that accepts/rejects, and a parser as something that builds a data structure. It's difficult to retrospectively find the literature, because outside of formal grammars recogniser _is_ used more loosely. But a few Wikipedia articles [1] [2] [3] and their referenced literature [4] [5] do agree with me. > A recognizer is an algorithm which takes as input a string and
> either accepts or rejects it depending on whether or not the string
> is a sentence of the grammar. A parser is a recognizer which also
> outputs the set of all legal derivation trees for the string. [1] https://en.wikipedia.org/wiki/Parsing#Computer_languages [2] https://en.wikipedia.org/wiki/Earley_parser#Earley_recognise... [3] https://en.wikipedia.org/wiki/CYK_algorithm#Generating_a_par... [4] http://reports-archive.adm.cs.cmu.edu/anon/anon/usr/ftp/scan... [5] http://bat8.inria.fr/~lang/papers/harder/harder.pdf |