SLR1Parser Class Reference

Implements an SLR(1) parser for context-free grammars. More...

#include <slr1_parser.hpp>

Collaboration diagram for SLR1Parser:

Classes
struct	s_action

Public Types
enum class	Action { Shift , Reduce , Accept , Empty }
	Represents the possible actions in the SLR(1) parsing table. More...
using	action_table
	Represents the action table for the SLR(1) parser.
using	transition_table
	Represents the transition table for the SLR(1) parser.

Public Member Functions
	SLR1Parser ()=default
	SLR1Parser (Grammar gr)
std::unordered_set< Lr0Item >	AllItems () const
	Retrieves all LR(0) items in the grammar.
void	Closure (std::unordered_set< Lr0Item > &items)
	Computes the closure of a set of LR(0) items.
void	ClosureUtil (std::unordered_set< Lr0Item > &items, unsigned int size, std::unordered_set< std::string > &visited)
	Helper function for computing the closure of LR(0) items.
std::unordered_set< Lr0Item >	Delta (const std::unordered_set< Lr0Item > &items, const std::string &str)
	Computes the GOTO transition (δ) for a given set of LR(0) items and a symbol.
bool	SolveLRConflicts (const state &st)
	Resolves LR conflicts in a given state.
void	First (std::span< const std::string > rule, std::unordered_set< std::string > &result)
	Calculates the FIRST set for a given production rule in a grammar.
void	ComputeFirstSets ()
	Computes the FIRST sets for all non-terminal symbols in the grammar.
void	ComputeFollowSets ()
	Computes the FOLLOW sets for all non-terminal symbols in the grammar.
std::unordered_set< std::string >	Follow (const std::string &arg)
	Computes the FOLLOW set for a given non-terminal symbol in the grammar.
void	MakeInitialState ()
	Creates the initial state of the parser's state machine.
bool	MakeParser ()
	Constructs the SLR(1) parsing tables (action and transition tables).
std::string	PrintItems (const std::unordered_set< Lr0Item > &items) const
	Returns a string representation of a set of LR(0) items.

Public Attributes
Grammar	gr_
	The grammar being processed by the parser.
std::unordered_map< std::string, std::unordered_set< std::string > >	first_sets_
	Cached FIRST sets for all symbols in the grammar.
std::unordered_map< std::string, std::unordered_set< std::string > >	follow_sets_
	Cached FOLLOW sets for all non-terminal symbols in the grammar.
action_table	actions_
	The action table used by the parser to determine shift/reduce actions.
transition_table	transitions_
	The transition table used by the parser to determine state transitions.
std::unordered_set< state >	states_
	The set of states in the parser's state machine.

Detailed Description

Implements an SLR(1) parser for context-free grammars.

This class builds an SLR(1) parsing table and LR(0) automaton from a given grammar. It provides methods for computing closure sets, GOTO transitions, constructing states, and performing syntax analysis using the generated table.

Member Typedef Documentation

action_table

using SLR1Parser::action_table

Initial value:

 
        std::map<unsigned int, std::map<std::string, SLR1Parser::s_action>>

Represents the action table for the SLR(1) parser.

The action table is a map that associates each state and input symbol with a specific action (Shift, Reduce, Accept, or Empty). It is used to determine the parser's behavior during the parsing process.

The table is structured as:

• Outer map: Keys are state IDs (unsigned int).
• Inner map: Keys are input symbols (std::string), and values are s_action structs representing the action to take.

transition_table

using SLR1Parser::transition_table

Initial value:

 
        std::map<unsigned int, std::map<std::string, unsigned int>>

Represents the transition table for the SLR(1) parser.

The transition table is a map that associates each state and symbol with the next state to transition to. It is used to guide the parser's state transitions during the parsing process.

The table is structured as:

• Outer map: Keys are state IDs (unsigned int).
• Inner map: Keys are symbols (std::string), and values are the next state IDs (unsigned int).

Member Enumeration Documentation

Action

enum class SLR1Parser::Action

strong

Represents the possible actions in the SLR(1) parsing table.

This enumeration defines the types of actions that can be taken by the parser during the parsing process:

• Shift: Shift the input symbol onto the stack and transition to a new state.
• Reduce: Reduce a production rule and pop symbols from the stack.
• Accept: Accept the input as a valid string in the grammar.
• Empty: No action is defined for the current state and input symbol.

Enumerator
Shift
Reduce
Accept
Empty

Constructor & Destructor Documentation

SLR1Parser() [1/2]

SLR1Parser::SLR1Parser ( )

default

SLR1Parser() [2/2]

SLR1Parser::SLR1Parser ( Grammar gr )

explicit

Here is the call graph for this function:

Member Function Documentation

AllItems()

std::unordered_set< Lr0Item > SLR1Parser::AllItems

(

)

const

Retrieves all LR(0) items in the grammar.

This function returns a set of all LR(0) items derived from the grammar's productions. Each LR(0) item represents a production with a marker indicating the current position in the production (e.g., A → α•β).

Returns

A set of all LR(0) items in the grammar.

Closure()

void SLR1Parser::Closure

(

std::unordered_set< Lr0Item > &

items

)

Computes the closure of a set of LR(0) items.

This function computes the closure of a given set of LR(0) items by adding all items that can be derived from the current items using the grammar's productions. The closure operation ensures that all possible derivations are considered when constructing the parser's states.

Parameters

items

The set of LR(0) items for which to compute the closure.

Here is the call graph for this function:

Here is the caller graph for this function:

ClosureUtil()

void SLR1Parser::ClosureUtil	(	std::unordered_set< Lr0Item > &	items,
		unsigned int	size,
		std::unordered_set< std::string > &	visited )

Helper function for computing the closure of LR(0) items.

This function recursively computes the closure of a set of LR(0) items by adding items derived from non-terminal symbols. It avoids redundant work by tracking visited non-terminals and stopping when no new items are added.

Parameters

items	The set of LR(0) items being processed.
size	The size of the items set at the start of the current iteration.
visited	A set of non-terminals that have already been processed.

Here is the call graph for this function:

Here is the caller graph for this function:

ComputeFirstSets()

void SLR1Parser::ComputeFirstSets

(

)

Computes the FIRST sets for all non-terminal symbols in the grammar.

This function calculates the FIRST set for each non-terminal symbol in the grammar by iteratively applying a least fixed-point algorithm. This approach ensures that the FIRST sets are fully populated by repeatedly expanding and updating the sets until no further changes occur (i.e., a fixed-point is reached).

Here is the call graph for this function:

Here is the caller graph for this function:

ComputeFollowSets()

void SLR1Parser::ComputeFollowSets

(

)

Computes the FOLLOW sets for all non-terminal symbols in the grammar.

The FOLLOW set of a non-terminal symbol A contains all terminal symbols that can appear immediately after A in any sentential form derived from the grammar's start symbol. Additionally, if A can be the last symbol in a derivation, the end-of-input marker ($) is included in its FOLLOW set.

This function computes the FOLLOW sets using the following rules:

1. Initialize FOLLOW(S) = { $ }, where S is the start symbol.
2. For each production rule of the form A → αBβ:
   • Add FIRST(β) (excluding ε) to FOLLOW(B).
   • If ε ∈ FIRST(β), add FOLLOW(A) to FOLLOW(B).
3. Repeat step 2 until no changes occur in any FOLLOW set.

The computed FOLLOW sets are cached in the follow_sets_ member variable for later use by the parser.

Note

This function assumes that the FIRST sets for all symbols have already been computed and are available in the first_sets_ member variable.

See also

First

follow_sets_

Here is the call graph for this function:

Here is the caller graph for this function:

Delta()

std::unordered_set< Lr0Item > SLR1Parser::Delta	(	const std::unordered_set< Lr0Item > &	items,
		const std::string &	str )

Computes the GOTO transition (δ) for a given set of LR(0) items and a symbol.

This function is equivalent to the δ(I, X) function in LR parsing, where it computes the set of items reached from a state I via symbol X.

Parameters

items	The current set of LR(0) items (state).
str	The grammar symbol used for the transition.

Returns

The resulting item set after the GOTO transition.

Here is the call graph for this function:

First()

void SLR1Parser::First	(	std::span< const std::string >	rule,
		std::unordered_set< std::string > &	result )

Calculates the FIRST set for a given production rule in a grammar.

The FIRST set of a production rule contains all terminal symbols that can appear at the beginning of any string derived from that rule. If the rule can derive the empty string (epsilon), epsilon is included in the FIRST set.

This function computes the FIRST set by examining each symbol in the production rule:

• If a terminal symbol is encountered, it is added directly to the FIRST set, as it is the starting symbol of some derivation.
• If a non-terminal symbol is encountered, its FIRST set is recursively computed and added to the result, excluding epsilon unless it is followed by another symbol that could also lead to epsilon.
• If the entire rule could derive epsilon (i.e., each symbol in the rule can derive epsilon), then epsilon is added to the FIRST set.

Parameters

rule	A span of strings representing the production rule for which to compute the FIRST set. Each string in the span is a symbol (either terminal or non-terminal).
result	A reference to an unordered set of strings where the computed FIRST set will be stored. The set will contain all terminal symbols that can start derivations of the rule, and possibly epsilon if the rule can derive an empty string.

Here is the call graph for this function:

Here is the caller graph for this function:

Follow()

std::unordered_set< std::string > SLR1Parser::Follow

(

const std::string &

arg

)

Computes the FOLLOW set for a given non-terminal symbol in the grammar.

The FOLLOW set for a non-terminal symbol includes all symbols that can appear immediately to the right of that symbol in any derivation, as well as any end-of-input markers if the symbol can appear at the end of derivations. FOLLOW sets are used in LL(1) parsing table construction to determine possible continuations after a non-terminal.

Parameters

arg	Non-terminal symbol for which to compute the FOLLOW set.

Returns

An unordered set of strings containing symbols that form the FOLLOW set for arg.

Here is the caller graph for this function:

MakeInitialState()

void SLR1Parser::MakeInitialState

(

)

Creates the initial state of the parser's state machine.

This function initializes the starting state of the parser by computing the closure of the initial set of LR(0) items derived from the grammar's start symbol. The initial state is added to the states_ set, and its transitions are prepared for further processing in the parser construction.

See also

states_

transitions_

Here is the call graph for this function:

Here is the caller graph for this function:

MakeParser()

bool SLR1Parser::MakeParser

(

)

Constructs the SLR(1) parsing tables (action and transition tables).

This function builds the SLR(1) parsing tables by computing the canonical collection of LR(0) items, generating the action and transition tables, and resolving conflicts (if any). It returns true if the grammar is SLR(1) and the tables are successfully constructed, or false if a conflict is detected that cannot be resolved.

Returns

true if the parsing tables are successfully constructed, false if the grammar is not SLR(1) or a conflict is encountered.

See also

actions_

transitions_

states_

Here is the call graph for this function:

Here is the caller graph for this function:

PrintItems()

std::string SLR1Parser::PrintItems

(

const std::unordered_set< Lr0Item > &

items

)

const

Returns a string representation of a set of LR(0) items.

This function converts a set of LR(0) items into a human-readable string, including dot positions, to help visualize parser states.

Parameters

items

The set of LR(0) items to print.

Returns

A formatted string representation of the items.

SolveLRConflicts()

bool SLR1Parser::SolveLRConflicts

(

const state &

st

)

Resolves LR conflicts in a given state.

This function attempts to resolve shift/reduce or reduce/reduce conflicts in a given state using SLR(1) parsing rules. It checks the FOLLOW sets of non-terminals to determine the correct action and updates the action table accordingly.

Parameters

st	The state in which to resolve conflicts.

Returns

true if all conflicts are resolved, false if an unresolvable conflict is detected.

Here is the call graph for this function:

Member Data Documentation

actions_

action_table SLR1Parser::actions_

The action table used by the parser to determine shift/reduce actions.

first_sets_

std::unordered_map<std::string, std::unordered_set<std::string> > SLR1Parser::first_sets_

Cached FIRST sets for all symbols in the grammar.

follow_sets_

std::unordered_map<std::string, std::unordered_set<std::string> > SLR1Parser::follow_sets_

Cached FOLLOW sets for all non-terminal symbols in the grammar.

gr_

Grammar SLR1Parser::gr_

The grammar being processed by the parser.

states_

std::unordered_set<state> SLR1Parser::states_

The set of states in the parser's state machine.

transitions_

transition_table SLR1Parser::transitions_

The transition table used by the parser to determine state transitions.

---

The documentation for this class was generated from the following files:

• backend/slr1_parser.hpp
• backend/slr1_parser.cpp