Context-Free Grammars Metrics

List of the used metrics for assessing the quality of Context-Free Grammars

Size Metrics

  1. Grammar Size

    2. Parameter Description
    #T number of terminal symbols
    #N number of non-terminal symbols
    #P number of productions
    #UP number of unit productions
    #R number of symbols directly or indirectly recursive
    &RHS average number of symbols in the right hand sides
    &RHS-Max maximum number of symbols on a right side, $max(length(RHS))$
    &Alt average number of alternative productions for the same left sides
    &Alt-Max maximum number of alternative productions for the same left side
    #Mod number of imported grammatical modules

  2. Syntax Complexity

    3. Parameter Description
    FanIn average number of branches of the input nodes (non-terminals) of the DGS
    FanOut average number of branches of the output nodes of the DGS

  3. Parser Size

    4. Parameter Description
    #RD number of functions from the Recursive-Descent Pure Parser
    TabLL dimension of the Parsing Table LL(1)
    AD-LR dimension of the Deterministic Automaton LR(0)
    TabsLR dimension of the Parsing Tables LR(0)

Style Metrics

  • Form of Recursion

    • Parameter Description
    DirectRec all recursion cases follow the pattern X -> ... X ...
    IndirectRec all recursion cases follow the pattern X -> ...Y ... ;Y -> ... X ...
    FMixedRec both forms of recursion are used

  • Type of Recursion

    • Parameter Description
    RecR DirectRec cases follow the recursive right pattern X -> ε| e X
    RecR-LL DirectRec cases follow the recursive LL(1) pattern X-> e C;C-> ε| e X
    IndirectRec DirectRec cases follow the recursive left pattern X-> ε| X e
    TMixedRec several direct recursion patterns are used

  • Notation

    • Parameter Description
    BNF all notations are written in Backus-Naur Form pure
    ex-BNF all notations are written in Extended Backus-Naur Form
    MixedN both notations are used

Lexicographic Metrics

  • Clear Identifiers

    • Number of terminals and non-terminals symbols in which the identifier derives from the concept name.

  • Keywords and clear Signs

    • Number of cases in which the keyword derives from the concept name.

  • Flexibility of terminals-variables

    • Number of terminals with flexibility on the value or identifier construction (T-variable).

  • Kind of Comments: inline + block + metaI

    • Parameter Description
    inline 1 if accepts comments from one point to the EOF;otherwise 0
    block 1 if accepts comments formed by blocks with one or more lines;otherwise 0
    metaI 1 if accepts meta-information inside the comments blocks;otherwise 0