diff -r f512026d5d6e -r 1abf8586ee6b csupp.tex --- a/csupp.tex Fri Nov 11 23:38:10 2011 +0000 +++ b/csupp.tex Sun Nov 20 22:53:50 2011 +0000 @@ -43,7 +43,8 @@ it increasingly clear, that this is not true anymore~\cite{Might11}. And there is a real practical need for new results: for example the future HTML5 Standard abandons a well-defined grammar specification, in favour of a bespoke -parser given as pseudo code. +parser given as pseudo code. Proving any property about this parser is nearly +impossible. This work targets parsers from a certification point of view. Increasingly, parsers are part of certified compilers, like @@ -77,7 +78,7 @@ (CFGs). This extension introduces new regular operators, such as negation and conjunction, on the right-hand side of grammar rules, as well as priority orderings for rules. With these extensions, PEG parsing becomes much -more powerful and more useful in practise. For example disambiguation, formerly expressed by semantic +more powerful and more useful in practice. For example disambiguation, formerly expressed by semantic filters, can now be expressed directly using grammar rules. However, there is a serious limitation of PEGs, which affects potential @@ -93,9 +94,9 @@ parsing. There are also good indications that we can adapt work on Boolean Grammars~\cite{Okhotin04}, which are similar to PEGs and for which the paper~\cite{KountouriotisNR09} gives a fixed-point semantics -to negation operators, but not to the Kleene star. +for negation operators, but not to the Kleene star. -For the parsing algorithm, we might be able to build upon +For our parsing algorithm, we might be able to build upon the classic Cocke-Younger-Kasami (CYK) algorithms~\cite{KountouriotisNR09} and Early~\cite{AycHor02, Earley70} parsers. The defect of CYK algorithms, however,