glr.h File Reference

Generalized LR (GLR) parser support for Lime. More...

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>

Go to the source code of this file.

Data Structures
struct	GLRParser
	GLR parser context, wrapping an underlying LALR(1) parser. More...
struct	GSSNode
	Graph-Structured Stack (GSS) node for GLR parsing. More...

Typedefs
typedef int(*	GLRDisambiguateFn) (uint32_t rule1_index, uint32_t rule2_index, void *user_data)
	User-provided disambiguation callback.

Functions
bool	glr_parser_accepted (const GLRParser *parser, uint16_t accept_action)
	Check if the parse completed successfully.
GLRParser *	glr_parser_create (uint32_t initial_state, size_t arena_size)
	Create a GLR parser.
void	glr_parser_destroy (GLRParser *parser)
	Destroy a GLR parser and free all resources.
int	glr_parser_feed (GLRParser *parser, const ParserSnapshot *snap, uint16_t token)
	Feed a token to the GLR parser.
uint32_t	glr_parser_head_count (const GLRParser *parser)
	Return the number of active parse heads.
void	glr_parser_set_disambiguate (GLRParser *parser, GLRDisambiguateFn fn, void *user_data)
	Set the disambiguation callback.
GSSNode *	gss_node_acquire (GSSNode *node)
void	gss_node_add_predecessor (GSSNode *node, GSSNode *pred)
GSSNode *	gss_node_create (LimeArena *arena, uint32_t state)
void	gss_node_release (GSSNode *node)
int	lime_parse_glr (struct ParseContext *ctx, GLRDisambiguateFn disambig, void *user_data)
	Enter GLR mode for an existing ParseContext.
bool	lime_parse_glr_accepted (struct ParseContext *ctx)
	Check whether the GLR parse accepted the input.
void	lime_parse_glr_end (struct ParseContext *ctx)
	Tear down GLR-mode state on the ParseContext.
int	lime_parse_glr_feed (struct ParseContext *ctx, uint16_t token)
	Feed one token into the GLR engine.
uint32_t	lime_parse_glr_head_count (struct ParseContext *ctx)
	Number of active parse heads.

Detailed Description

Generalized LR (GLR) parser support for Lime.

GLR parsing extends the underlying LALR(1) machinery so a runtime shift/reduce or reduce/reduce conflict produces a fork in the parse stack rather than an error. Heads that converge on the same parser state are merged. When two reductions produce the same nonterminal at the same position the user-provided disambiguation callback is consulted.

GLR is built on top of a Graph-Structured Stack (GSS) – each node is a parser state with reference-counted predecessor links, so two parallel parses can share a common prefix without copying the stack.

The GLR engine consumes the same ParserSnapshot tables that the LALR runtime drives. No code generation changes are needed: any grammar that compiles to a snapshot can be parsed in either mode.

When to use GLR

Use GLR for grammars that are inherently ambiguous (natural-language parsers, dialect-rich SQL with overloaded operators, scope-sensitive syntactic categories) or when you want to avoid hand-encoding lookahead in semantic actions. For unambiguous grammars LALR is faster – see docs/GLR.md for measured numbers.

See also

docs/GLR.md, tests/test_glr_no_conflict.c, tests/test_glr_ambiguous.c

Definition in file glr.h.

Typedef Documentation

GLRDisambiguateFn

typedef int(* GLRDisambiguateFn) (uint32_t rule1_index, uint32_t rule2_index, void *user_data)

User-provided disambiguation callback.

Called when two reductions produce the same non-terminal at the same position (i.e., two GSS heads merge at the same state). Returns 1 to prefer rule1, 2 to prefer rule2, 0 for ambiguity error.

Definition at line 78 of file glr.h.

Function Documentation

glr_parser_accepted()

bool glr_parser_accepted	(	const GLRParser *	parser,
		uint16_t	accept_action
	)

Check if the parse completed successfully.

Parameters

parser	Active GLR parser.
accept_action	Snapshot accept-action constant.

Returns

true iff exactly one live head sits in the accept state.

glr_parser_create()

GLRParser * glr_parser_create	(	uint32_t	initial_state,
		size_t	arena_size
	)

Create a GLR parser.

Parameters

initial_state	The LALR start state (typically 0).
arena_size	Initial arena block size (0 for the default 64 KiB).

Returns

New GLR parser, or NULL on allocation failure.

glr_parser_destroy()

void glr_parser_destroy

(

GLRParser *

parser

)

Destroy a GLR parser and free all resources.

Passing NULL is safe.

glr_parser_feed()

int glr_parser_feed	(	GLRParser *	parser,
		const ParserSnapshot *	snap,
		uint16_t	token
	)

Feed a token to the GLR parser.

For each active stack head, the snapshot's action table is consulted. When both a shift and a reduce are valid (S/R conflict) the head is forked: one copy shifts, the other reduces. After processing all heads, heads that arrived at the same state are merged into one.

The snapshot supplies every constant that the original 19-parameter version of this function took – the action arrays, the dispatch range constants (yy_min_shiftreduce, yy_min_reduce, ...), and the per-rule LHS/nrhs metadata. Pass the same snapshot pointer that was used to drive the LALR engine.

Parameters

parser	Active GLR parser.
snap	Snapshot whose action tables to consult.
token	Terminal symbol code.

Return values

0	Success.
-1	Unresolvable ambiguity (no disambiguation callback set and two heads converged).
-2	All heads died (syntax error on every active path).

glr_parser_head_count()

uint32_t glr_parser_head_count

(

const GLRParser *

parser

)

Return the number of active parse heads.

Return values

1	Unambiguous (single live head).
>1	Ambiguous prefix; multiple heads still live.
0	All heads died.

glr_parser_set_disambiguate()

void glr_parser_set_disambiguate	(	GLRParser *	parser,
		GLRDisambiguateFn	fn,
		void *	user_data
	)

Set the disambiguation callback.

Parameters

parser	Active GLR parser.
fn	Callback function (NULL to clear).
user_data	Opaque pointer passed back into fn.

lime_parse_glr()

int lime_parse_glr	(	struct ParseContext *	ctx,
		GLRDisambiguateFn	disambig,
		void *	user_data
	)

Enter GLR mode for an existing ParseContext.

Parameters

ctx	Active ParseContext (from parse_begin).
disambig	Disambiguation callback (NULL = report ambiguity).
user_data	Opaque pointer passed to disambig callback.

Returns

0 on success, non-zero on failure.

lime_parse_glr_feed()

int lime_parse_glr_feed	(	struct ParseContext *	ctx,
		uint16_t	token
	)

Feed one token into the GLR engine.

Return values

0	Token consumed successfully.
-1	Unresolvable ambiguity.
-2	All parse heads died.