Puppy.Runtime

type Table tok val = { action :: Int -> Int -> Action, endTerminal :: Int, goto :: Int -> Int -> Int, production :: Int -> ProductionInfo, recovery :: Maybe (Recovery tok val), semanticAction :: Int -> Array val -> val, startState :: Int, terminalIndex :: tok -> Int, terminalName :: Int -> String, terminalValue :: tok -> val }

Everything a generated module supplies. val is the type the generated code boxes every semantic value into; the driver only ever moves those values around, so it never needs to look inside one.

data Step tok val

What the parser did with the token it was given.

Constructors

• Await (Resume tok val)
• Done val
• Failed (ParseError tok)

newtype Resume tok val

A parser stopped for want of a token.

Opaque on purpose. What is inside is the two stacks and the invariant between them, and a caller who could take it apart could put it back together wrong; resume and unexpectedEnd are the whole of what may be done with one.

data RecoveryResult tok val

What came of a parse that was allowed to carry on past an error.

Three answers rather than two, because "it parsed" and "it parsed, and here is what was wrong with it" are different things to be told and a caller acts differently on each. The errors are in the order they were found.

Constructors

• ParseSucceeded val
• ParseRecovered (Array (ParseError tok)) val
• ParseFailed (Array (ParseError tok))

Instances

• (Eq tok, Eq val) => Eq (RecoveryResult tok val)
• (Show tok, Show val) => Show (RecoveryResult tok val)

type Recovery tok val = { terminal :: Int, value :: ParseError tok -> val }

What a parse needs in order to carry on past an error.

One thing rather than two, because a terminal number with no way to make a value for it, or a value with no terminal to attach it to, is not half of anything. terminal is one past endTerminal: recovery is the only thing that names it, terminalIndex never returns it, and nothing lists it among the tokens that were expected.

type ProductionInfo = { arity :: Int, lhs :: Int, name :: String }

What the driver needs to know about a production in order to reduce by it.

type ParseError tok = { expected :: Array String, found :: Maybe tok, position :: Int, state :: Int }

type Action = Int

One cell of the LR action table, indexed by (state, terminal), as an Int.

  0        the token is an error here
  1        accept
  n >= 2   shift, and go to state n - 2
  n < 0    reduce by production -n - 1

A number rather than a constructor, because of how many of these there are. A table with a cell for every (state, terminal) pair is read by index instead of searched, which is the whole point of an LR parser being a table -- and a cell for every pair is affordable as a number and is not affordable as an object. For a real grammar the difference is a table half the size that answers in one read instead of a scan.

Build them with the four below rather than by arithmetic.

unexpectedEnd :: forall tok val. Resume tok val -> ParseError tok

The error a parser is owed when its supply of tokens runs out.

This is not how a parse is finished. A grammar ends on a terminal of its own -- Nothing, for a generated parser -- and a caller who has one to give should call resume with it. This is for a caller who has not: the array ran off the end, the file was truncated, the socket closed.

It is a function rather than a field of Await because expected costs a pass over every terminal in the grammar. Computing it each time the parser stopped for a token would make parsing cost the length of the input times the size of the alphabet, to answer a question almost no caller asks.

start :: forall tok val. Table tok val -> Step tok val

A parser that has read nothing yet, waiting for the first token.

shift :: Int -> Action

Consume the lookahead and move to the given state.

resume :: forall tok val. Resume tok val -> tok -> Step tok val

Give the parser the token it asked for.

offer above is the loop; this is the answer a caller who is not going to carry on past an error wants to hear, which is the same one with the stacks left out of the failure.

reduce :: Int -> Action

Apply the production with the given index.

parseRecoveringAt :: forall tok val. Table tok val -> (Int -> tok) -> RecoveryResult tok val

Parse from something a caller can look up by position, recovering where it can.

at has to be total, and out past the end of the input it has to keep answering with the terminal the grammar ends on. A generated module gets that for nothing: its driver token is a Maybe, and looking past the end of an array is Nothing, which is the end of input as far as the tables are concerned.

There is no second loop here. Reading by position is a token source like any other once it is given somewhere to keep the position, so this is parseMRecovering with that somewhere -- and no copy of the input is made on the way.

parseMRecovering :: forall m tok val. MonadRec m => Table tok val -> m tok -> m (RecoveryResult tok val)

Parse from tokens pulled one at a time, carrying on past what it can.

The same LR loop as parseM, read one case further: where that one stops at a failure, this one looks for somewhere the grammar said a parse may be picked up again, puts an ERROR there, and then throws tokens away until it finds one the parser can take.

canConsume is what "can take" means, and it has to be that rather than the cheaper question. A token the top state would reduce on and the state underneath would reject is not one to carry on from; taking it would fail again immediately and the parser would throw the next one away for the same reason, all the way to the end.

End of input is where this stops. A parser that cannot take it has nowhere left to go, and asking the source for another token after it has said there are none is asking a question that has already been answered.

parseM :: forall m tok val. MonadRec m => Table tok val -> m tok -> m (Either (ParseError tok) val)

Run the LR automaton over tokens pulled one at a time.

The action is run exactly when the parser wants a token, and not once after it has an answer: a parse that accepts or fails on the token it is holding does not ask for another. There is no need for the source to know when to stop, only what to say at the end, which for a generated parser is Nothing.

Whatever else m can do, the source may do while lexing. Failing is the useful case -- a lexer that meets a character it cannot read wants to say so, and in ExceptT or Aff saying so abandons the parse without the driver needing an opinion about it.

MonadRec rather than Monad because the loop is as long as the input.

parse :: forall tok val. Table tok val -> Array tok -> Either (ParseError tok) val

Run the LR automaton over an array of tokens.

The array must be terminated by whatever token the grammar declared as its end marker; this does not append one. Running off the end is therefore reported as an error rather than treated as end of input -- see unexpectedEnd.

errorAction :: Action

The token cannot appear here.

canConsume :: forall tok val. Resume tok val -> tok -> Boolean

Whether the parser could take this token, without taking it.

A question about the tables and the state stack, and about nothing else. A reduction on the way to the answer is followed on the states alone: no semantic value is unboxed, terminalValue is never asked what the token carries and semanticAction is never run. Answering has no cost beyond the reductions it walks and leaves nothing behind, so the same Resume can be asked about as many tokens as a caller likes.

true includes accepting. A token that ends the parse is one the parser can take, which is what a caller looking for somewhere to carry on from wants to hear -- the alternative is a caller that walks past the end of a complete parse looking for a better place.

expected is not a substitute for this. That is the cheap approximation every LR parser reports: it asks the top state alone and so can name a token that the reduction underneath would have rejected. This follows the reductions, and so answers exactly.

acceptAction :: Action

The input is complete.

data Value

unbox :: forall a. Value -> a

slot :: Int -> Array Value -> Value

One of the values a production is reducing over.

The driver hands a semantic action exactly as many values as the production has symbols, so an index the generator emitted can only be out of range if the tables and the actions disagree -- which is a bug in the generator, not something a grammar can cause.

internalError :: forall a. String -> a

Something the generator promised would not happen.

Reserved for broken tables. Nothing a grammar or an input can do should reach one of these; a parse error is an Either, not a crash.

box :: forall a. a -> Value