Whenever I read about equality I took it for granted, but few days ago I wondered if my understanding is not too shallow. Consider such example (taken from: http://david.tribble.com/text/honalee.html):

Expr -> Expr '+' . Term
Term -> '+' . Term     
Term -> . Factor

Usually it is all about SLR(0) equality so in short, two items are equal if they have all the same symbols and they are in the same state (the dot is in the same place). I didn't see anything else than such notion/definition.

My new approach is somewhat different -- let's add user actions:

Expr -> Expr '+' . Term @user_func1
Term -> '+' . Term @user_func2
Term -> . Factor  @user_func3

I would say that two items are equal, if:

  • LHS symbol is the same
  • and the number of seen symbols is the same (*)
  • and the unseen symbols are the same
  • and the user action is exactly the same

For example -- such items would be the same:

elem -> ASTERISK . ID @func1;
elem -> ID . ID @func1;

This change of equality idea gave me 10% gain on table sizes, and now I wonder if I miss something:

  • maybe there is even "better" definition of equality (like dropping (*) condition)
  • or -- my definition is wrong



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.