CFG Plugin2.0 Input Syntax

From FSL
Jump to: navigation, search

The MOP CFG plugin uses the following syntax, which is defined in BNF:

// BNF below is extended with {p} for zero or more and [p] for zero or one repetitions of p
// The plugin syntax
<Plugin Input> ::= {<Event} <CFG Name> ":" <CFG Syntax>
<Event> ::= "event" <Event Name>
<Event Name> ::= <Id>
// The mandatory MOP logic syntax
<CFG Name> ::= "lr" | "lalr" | "lr_lazy" | "lalr_lazy"
<CFG Syntax> ::= <Production> {"," <Production>}
<CFG State> ::= "match" | "fail"
// The auxiliary elements for the logic syntax
<Production> ::= <NonTerminal Name> "->" <Right Hand Side> {"|" <Right Hand Side>}
<Right Hand Side> ::= <NonTerminal or Event Name> { <NonTerminal or EventName> } | "epsilon"
<NonTerminal or EventName> ::= <NonTerminal Name> | <Event Name>

<Plugin Input>

The input syntax for this plugin consists of event definitions (<Event>), the logic name (<CFG Name>), followed by a colon and then a context free grammar (<CFG Syntax>).


<Event> defines a name that may be used in the context free grammar.

<Event Name>

An identifier to represent an event.

<CFG Name>

<CFG Name> instantiates <Logic Name> from the MOP Syntax. It denotes the CFG logic using the one of the strings "lr", "lalr", "lr_lazy", or "lalr_lazy". If "lr_lazy" or "lalr_lazy" is specified, error tokens are thrown away after the pattern match fail is reported, this allows one to capture multiple failures (see example SafeLock). "lr" and "lalr" behave like ERE and FSM in that if there is a bad event, the failure is reported and the monitor stays "stuck" in the error state. Using "lalr" instead of "lr", the tables will be minimized using the LALR state merger optimization.

<CFG Syntax>

<CFG Syntax> instantiates <Logic Syntax> from the MOP Syntax. It defines a context free grammar, which is composed of multiple <Production>s.

<CFG State>

<CFG State> instantiates <Logic State> from the MOP Syntax. In a CFG specification, <CFG State> can be either the special state match or fail. match corresponds to a situation wherein the trace matches the specified pattern, whereas fail occurs when the trace is not a prefix of any matching trace. The CFG monitor is unable to leave the fail state once it is entered, unless one of the lazy <CFG Name>s are used.


A <Production> is a pair of <NonTerminal Name> and possibly several alternate <Right Hand Side>s, separated by an "->", which specifies that a given <Right Hand Side> can be replaced by the <NonTerminal Name> in the considered input (which is stored in a stack). This process is called a reduction, and may cause the input to match a new <Right Hand Side>, causing another reduction. The <NonTerminal Name> of the first production is considered to be the start symbol, which defines the root of the grammar. A valid trace must eventually reduce to the start symbol.

<Right Hand Side>

A <Right Hand Side> can be either a string of <Nonterminal or Event Name>s or the empty string "epsilon".

<NonTerminal or Event Name>

<NonTerminal or Event Name> can match either a <NonTerminal Name> or an <Event Name>.

<NonTerminal Name>

<NonTerminal Name> is an identifier that can be used as a nonterminal.


event a 
event b
lr:  S -> b S b | b A b | epsilon, 
      A -> A a | a

This example monitors the language b^n a* b^n using LR tables.

Personal tools