<commit_before>\documentclass{amsart}
\usepackage{algpseudocode}

\newcommand{\comment}[1]{}
\newcommand{\myspace}{\mbox{ }\ \ \ \ }
\newcommand{\myspacem}{\;\;\;\;\;}
\newcommand{\sep}{\,\mid\,}
\newcommand{\mydot}{\raisebox{.15em}{\tiny $\,\bullet\,$}}
\newcommand{\size}[1]{\left | {#1} \right |} 
\newcommand{\rank}[1]{\mbox{$r({#1})$}} 
\newcommand{\order}[1]{O(#1)}

\newcommand{\cfg}{CFG}

\newcommand{\nonterm}{\mbox{$V_{{\rm N}}$}}
\newcommand{\myterm}{\mbox{$V_{{\rm T}}$}}

\newcommand{\de}{\rightarrow}
\newcommand{\derivg}[1]{\mathrel{\mbox{$\:\Rightarrow\:$}}}
\newcommand{\derivrg}[2]{\mathrel{\mbox{$\:\stackrel{\!{#1}}%
        {\Rightarrow\!}\:$}}}

\newcommand{\rlc}{\mathrel{\angle}}
\newcommand{\rlcp}{\mathrel{\angle^+}}
\newcommand{\rlcm}{\mathrel{\angle^\ast}}
\newcommand{\ep}{\varepsilon}

\newcommand{\goto}{\mbox{{\it goto\/}}}
\newcommand{\prd}{\mbox{{\it prd\/}}}
\newcommand{\gto}{\mbox{$goto_1$}}
\newcommand{\gtt}{\mbox{$goto_2$}}

\newcommand{\eset}{I_{{\rm E}}}
\newcommand{\ieset}{I_{{\rm V}}}
\newcommand{\chartset}{I_{{\rm C}}}
\newcommand{\pred}{\mbox{{\it pred\/}}}

\newtheorem{alg}{Algorithm}%[section]

\hyphenation{ALGOL}

\begin{document}

\title{The Marpa Recognizer}

\author{<NAME>}

\begin{abstract}
This paper reports describes the recognizer portion
of the Marpa algorithm.
The Marpa algorithm is a practical, and fully implemented,
algorithm for the recognition,
parsing and evaluation of context-free grammars.
Marpa's recognizer is based
an Earley's algorithm,
and merges the improvements to Earley's
from Leo~\cite{LEO91}
and Aycock and Horspool~\cite{AH2002}.
Their combination in the marpa parse engine
has an added feature:
It makes available,
before each token is scanned,
full knowledge of the state of the parse so far.
This allows input to be altered as the parse progresses,
which can be an extremely powerful technique.
\end{abstract}

\maketitle

\section{Introduction}

Despite the promise of general context-free parsing,
and the strong academic literature behind it,
it has never been incorporated into a tool
as widely available as yacc or
regular expressions.
The Marpa project was begun to end this neglect by
pulling the best results from the literature,
and to turn them into a widely-available tool.
A stable version of this tool, Marpa::XS, was
delivered to the CPAN Perl archive on Solstice Day
in 2011.

Marpa::XS is a complete implementation of a parser
generator.
Its recognizer is built around a parse engine,
which is new, but which also owes a great debt
to previous work.

\section{Preliminaries}
\label{s:prel}

I assume familiarity with standard grammar notation
(pages 14-15 in~\cite{GJ2002}).
Let grammar 
$G$ be $(\myterm, \nonterm, P, S)$,
has been augmented with a dedicated start rule
$Start_{RULE} = [ Start_{SYM} \de S' ]$
and that the dedicated start symbol
$Start_{SYM}$ such that
$Start_{SYM} \in \nonterm, Start_{SYM} \neg S'$
appears only in $Start_{RULE}$.

In this paper a
"split LR(0) $\epsilon$-DFA"
a described by Aycock and Horspool~\cite{AH2002},
will be called an Aycock-Horspool Finite Automaton,
or AHFA.
Let FA be the AHFA derived from $G$.
as described in~\cite{AH2002}.

\section{AHFA States}
\label{s:AHFA}

A full description of how to derive an AHFA in theory
can be found in \cite{AH2002},
and examples of how to derive it in practice
can be found in the code for various release of Marpa.
Here I will just summarize the central ideas behind AHFA's.

Aycock and Horspool based their AHFA's
on a few observations.
First, in practice, Earley items with the same dotted rule
often appear in groups in the Earley sets,
where the entire shares the same origin.
Second, there was already in the literature a method
for associating groups of dotted rules that often appear together
when parsing.
This method was the LR(0) DFA used in the much-studied
LALR and LR parsers.
Third, the LR(0) items that are the components of LR(0)
states are, exactly, dotted rules.
Fourth, by taking into account symbols which derive the
null string, the LR(0) DFA could be turned into an
LR(0) $\epsilon$-DFA, which would be even more effective
at grouping dotted rules which occur together.

AHFA states are sets of dotted rules.
Aycock and Horspool realized that by changing Earley items
to track AHFA states, instead of individual dotted rules,
the size of Earley sets could be reduced,
and Earley's algorithm made faster in practice.
In short, then, AHFA states are a shorthand that Earley items
can use for groups of dotted rules that occur together frequently.
The original Earley items could be represented as $(r_{DOTTED}, origin)$
duples, where $r_{DOTTED}$ is a dotted rule.
Aycock and Horspool modified their Earley items to be $(L_{STATE}, origin)$
duples, where $L_{STATE}$ is an AHFA state.

\section{The Marpa Recognizer}
\label{s:recce}

\begin{algorithmic}[1] 
\Procedure{Scan}{$i,a$}
\Comment{Scan a token $a$, which starts at Earley set $i$}
\For{each Earley item $x_{EITEM}$ in $ES[i]$}
\State $to_{AHFA} \gets GOTO(x_{EITEM}.AHFA, a)$
\If{$to_{AHFA} \neg \Lambda$}
\State add Earley item $[to_{STATE}, origin]$ to $ES[i+1]$
\EndIf
\EndFor
\EndProcedure
\end{algorithmic} 

\section{Concluding Remarks}
\label{s:disc}

\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{AH2002}
John~Aycock and R.~Nigel~Horspool
\newblock Practical Earley Parsing
\newblock \em{The Computer Journal},
    Vol. 45, No. 6, 2002, pp. 620-630.
<commit_msg>Work on theory doc<commit_after>\documentclass{amsart}
\usepackage{algpseudocode}

\newcommand{\comment}[1]{}
\newcommand{\myspace}{\mbox{ }\ \ \ \ }
\newcommand{\myspacem}{\;\;\;\;\;}
\newcommand{\sep}{\,\mid\,}
\newcommand{\mydot}{\raisebox{.15em}{\tiny $\,\bullet\,$}}
\newcommand{\size}[1]{\left | {#1} \right |} 
\newcommand{\rank}[1]{\mbox{$r({#1})$}} 
\newcommand{\order}[1]{O(#1)}

\newcommand{\cfg}{CFG}

\newcommand{\nonterm}{\mbox{$V_{{\rm N}}$}}
\newcommand{\myterm}{\mbox{$V_{{\rm T}}$}}

\newcommand{\de}{\rightarrow}
\newcommand{\derivg}[1]{\mathrel{\mbox{$\:\Rightarrow\:$}}}
\newcommand{\derivrg}[2]{\mathrel{\mbox{$\:\stackrel{\!{#1}}%
        {\Rightarrow\!}\:$}}}

\newcommand{\rlc}{\mathrel{\angle}}
\newcommand{\rlcp}{\mathrel{\angle^+}}
\newcommand{\rlcm}{\mathrel{\angle^\ast}}
\newcommand{\ep}{\varepsilon}

\newcommand{\goto}{\mbox{{\it goto\/}}}
\newcommand{\prd}{\mbox{{\it prd\/}}}
\newcommand{\gto}{\mbox{$goto_1$}}
\newcommand{\gtt}{\mbox{$goto_2$}}

\newcommand{\eset}{I_{{\rm E}}}
\newcommand{\ieset}{I_{{\rm V}}}
\newcommand{\chartset}{I_{{\rm C}}}
\newcommand{\pred}{\mbox{{\it pred\/}}}

\newtheorem{alg}{Algorithm}%[section]

\hyphenation{ALGOL}

\begin{document}

\title{The Marpa Recognizer}

\author{<NAME>}

\begin{abstract}
This paper reports describes the recognizer portion
of the Marpa algorithm.
The Marpa algorithm is a practical, and fully implemented,
algorithm for the recognition,
parsing and evaluation of context-free grammars.
Marpa's recognizer is based
an Earley's algorithm,
and merges the improvements to Earley's
from Leo~\cite{LEO91}
and Aycock and Horspool~\cite{AH2002}.
Their combination in the marpa parse engine
has an added feature:
It makes available,
before each token is scanned,
full knowledge of the state of the parse so far.
This allows input to be altered as the parse progresses,
which can be an extremely powerful technique.
\end{abstract}

\maketitle

\section{Introduction}

Despite the promise of general context-free parsing,
and the strong academic literature behind it,
it has never been incorporated into a tool
as widely available as yacc or
regular expressions.
The Marpa project was begun to end this neglect by
pulling the best results from the literature,
and to turn them into a widely-available tool.
A stable version of this tool, Marpa::XS, was
delivered to the CPAN Perl archive on Solstice Day
in 2011.

Marpa::XS is a complete implementation of a parser
generator.
Its recognizer is built around a parse engine,
which is new, but which also owes a great debt
to previous work.

\section{Preliminaries}
\label{s:prel}

I assume familiarity with standard grammar notation
(pages 14-15 in~\cite{GJ2008}).
Let grammar 
$G$ be $(\myterm, \nonterm, P, S)$,
has been augmented with a dedicated start rule
$Start_{RULE} = [ Start_{SYM} \de S' ]$
and that the dedicated start symbol
$Start_{SYM}$ such that
$Start_{SYM} \in \nonterm, Start_{SYM} \neg S'$
appears only in $Start_{RULE}$.

In this paper a
"split LR(0) $\epsilon$-DFA"
a described by Aycock and Horspool~\cite{AH2002},
will be called an Aycock-Horspool Finite Automaton,
or AHFA.
Let FA be the AHFA derived from $G$.
as described in~\cite{AH2002}.

\section{AHFA States}
\label{s:AHFA}

A full description of how to derive an AHFA in theory
can be found in \cite{AH2002},
and examples of how to derive it in practice
can be found in the code for various release of Marpa.
Here I will just summarize the central ideas behind AHFA's.

Aycock and Horspool based their AHFA's
on a few observations.
First, in practice, Earley items with the same dotted rule
often appear in groups in the Earley sets,
where the entire shares the same origin.
Second, there was already in the literature a method
for associating groups of dotted rules that often appear together
when parsing.
This method was the LR(0) DFA used in the much-studied
LALR and LR parsers.
Third, the LR(0) items that are the components of LR(0)
states are, exactly, dotted rules.
Fourth, by taking into account symbols which derive the
null string, the LR(0) DFA could be turned into an
LR(0) $\epsilon$-DFA, which would be even more effective
at grouping dotted rules which occur together.

AHFA states are sets of dotted rules.
Aycock and Horspool realized that by changing Earley items
to track AHFA states, instead of individual dotted rules,
the size of Earley sets could be reduced,
and Earley's algorithm made faster in practice.
In short, then, AHFA states are a shorthand that Earley items
can use for groups of dotted rules that occur together frequently.
The original Earley items could be represented as $(r_{DOTTED}, origin)$
duples, where $r_{DOTTED}$ is a dotted rule.
Aycock and Horspool modified their Earley items to be $(L_{STATE}, origin)$
duples, where $L_{STATE}$ is an AHFA state.

\section{The Marpa Recognizer}
\label{s:recce}

Scan a token $a$, which starts at Earley set $i$.
\begin{algorithmic}[1] 
\Procedure{Scan}{$i,a$}
\Comment{Scan a token $a$, which starts at Earley set $i$}
\For{each Earley item $x_{EITEM}$ in $ES[i]$}
\State $to_{AHFA} \gets GOTO(x_{EITEM}.AHFA, a)$
\State $AddState(i+1, to_{AHFA}, x_{EITEM}.origin)$
\If{$to_{AHFA} \neg \Lambda$}
\State add Earley item $[to_{STATE}, origin]$ to $ES[i+1]$
\EndIf
\EndFor
\EndProcedure
\end{algorithmic} 

\begin{algorithmic}[1] 
\Procedure{Complete}{$i_{LOC}$}
\For{each Earley item $work_{EITEM} \in ES[i]$}
\For{each completed rule, $LHS_{SYM} \de RHS_{SYM}[0], ...$}
\For{each $predecessor_{EITEM} \in ES[work_{EITEM}.origin]$}
\State $to_{AHFA} \gets GOTO(predecessor_{EITEM}.AHFA, LHS_{SYM})$
\State $AddState(to_{AHFA}, predecessor_{EITEM}.origin)$
\EndFor
\EndFor
\EndFor
\EndProcedure
\end{algorithmic} 

\begin{algorithmic}[1] 
\Procedure{Add State}{$i_{LOC},discovered_{STATE},origin_{LOC}$}
\State $predicted_{STATE} \gets \Lambda$
\If{$to_{STATE} \neg \Lambda$}
\State add Earley item $[to_{STATE}, origin_{LOC}]$ to $ES[i]$
\State $predicted_{STATE} \gets GOTO(to_{STATE}, \epsilon)$
\EndIf
\If{$predicted_{AHFA} \neg \Lambda$}
\State add Earley item $[predicted_{STATE}, i]$ to $ES[i]$
\EndIf
\EndProcedure
\end{algorithmic} 

\section{Concluding Remarks}
\label{s:disc}

\bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{AH2002}
John~Aycock and R.~Nigel~Horspool
\newblock Practical Earley Parsing
\newblock \em{The Computer Journal},
    Vol. 45, No. 6, 2002, pp. 620-630.

{'fraction_non_alphanumeric': 0.13641345586375517, 'fraction_numerical': 0.012309248798583593, 'mean_word_length': 4.90443006470881, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4711718', 'n_tokens_mistral': 4039, 'n_tokens_neox': 3742, 'n_words': 1416}