实现使用反讽一个前缀符号表达式解析器 [英] Implementing a prefix notation expression parser using Irony

问题描述

我试图解析使用上下文无关文法与反讽库用户输入的前缀符号逻辑表达式。这是一个课堂作业，所以如果有人恰好是这方面的专家，我很想知道更多。

我要接受用户输入的逻辑表达式格式如下：

 和PQ  - （意为p ^ Q）
或PQ  - （意为p v Q）
非P  - （意思〜P）
小鬼PQ  - （意思对 - > Q）
  

我试图将这些解析为使用我实施反讽一个上下文无关文法表达式树。上下文无关文法我使用的是在这里，在BNF：

 <表达> :: =<不> | <和> | <或GT; | <&蕴涵GT; | <标识符GT; 
<不> :: =而不是<表达> 
<和> :: =和&所述;表达> <表达> 
<或GT; :: =或<表达> <表达> 
<&蕴涵GT; :: =小鬼<表达> <表达> 
 
（小于标识符>的作为IdentifierTerminal对象实现）。 
  

我用反讽来解析表达式之前，但由于某些原因，我无法得到它的工作。当我键入表达式和P Q 它似乎是确定和为标识的终端，而不是与非终结的一部分。我可能会做一些明显的，但我根本无法弄明白。这里是语文课我扩展：

<预类=郎CSHARP prettyprint-覆盖> 类LogicPrefix：语法
{
公共LogicPrefix（）
：基地（假）
{
非终结表达=新的非终结（表情）;
非终结蕴涵=新的非终结（暗示）;
非终结并=新的非终结（和）;
非终结或者=新的非终结（或者）;
非终结并非=新的非终结（不）;
终端标识=新IdentifierTerminal（标记）;
根=表达式;

Expression.Rule = AND |或者|没有|标识;

Not.Rule =而不是+表达;
Implies.Rule =小鬼+ +表达的表达;
And.Rule =和+表达+的表达;
Or.Rule =或+表达+的表达;

}
}


这是我的驱动程序类：

<预类=郎-CS prettyprint-覆盖> 类节目
{
静态无效的主要（字串[] args ）
{
LogicPrefix语法=新LogicPrefix（）;
分析器P =新的解析器（语法）;
是ParseTree PT = p.Parse（和P Q）;
// PT已抛出错误标志。
}
}


请让我知道，如果我做错事，我喜欢这方面的一些建议。

解决方案

您识别词法似乎让你的其他终端都可以lexed作为标识符，因为顾名思义 IdentifierTerminal 承认任何带有下划线或字母开头，只包含字母，数字和下划线（的来源）。这意味着，当你的程序读取和，它可以读取它作为标识符和或关键字<$ C 。$ C>和

它看起来像你对我可以通过声明你的运营商是标点符号使用以下行解决这个问题：

  MarkPunctuation（小鬼，和，或，非）
  

I'm trying to parse user-inputted prefix notation logical expressions using a context-free-grammar with the Irony library. This is for a class assignment so if anybody happens to be an expert on this, I would love to know more.

I need to accept a user-inputted logical expression of the following format:

and P Q -- (meaning P ^ Q)
or P Q -- (meaning P v Q)
not P  -- (meaning ~P)
imp P Q -- (meaning P -> Q)

I'm attempting to parse these into expression trees using a context free grammar I'm implementing in Irony. The context-free grammar I'm using is here, in BNF:

<Expression> ::= <Not> | <And> | <Or> | <Implies> | <Identifier>
<Not>        ::= "not" <Expression>
<And>        ::= "and" <Expression> <Expression>
<Or>         ::= "or" <Expression> <Expression>
<Implies>    ::= "imp" <Expression> <Expression>

(<Identifier> is implemented as an IdentifierTerminal object).

I've used Irony to parse expressions before but for some reason, I cannot get it to work. When I type the expression and P Q it seems to be identifying "and" as an Identifier terminal, not part of the And nonterminal. I may be doing something obvious but I simply can't figure it out. Here is the language class I extended:

class LogicPrefix : Grammar
{
    public LogicPrefix()
        : base(false)
    {
        NonTerminal Expression = new NonTerminal("expression");
        NonTerminal Implies = new NonTerminal("implies");
        NonTerminal And = new NonTerminal("and");
        NonTerminal Or = new NonTerminal("or");
        NonTerminal Not = new NonTerminal("not");
        Terminal Identifier = new IdentifierTerminal("identifier");
        Root = Expression;

        Expression.Rule = And | Or | Not | Identifier;

        Not.Rule = "not" + Expression;
        Implies.Rule = "imp" + Expression + Expression;
        And.Rule = "and" + Expression + Expression;
        Or.Rule = "or" + Expression + Expression;

    }
}

And here is my driver class:

class Program
{
    static void Main(string[] args)
    {
        LogicPrefix grammar = new LogicPrefix();
        Parser p = new Parser(grammar);
        ParseTree pt = p.Parse("and P Q");
        //pt has thrown an error flag.
    }
}

Please let me know if I'm doing something wrong, I'd love some advice on this.

解决方案

Your identifier lexing seems to allow your other terminals to be lexed as identifiers because by definition IdentifierTerminal recognizes anything that "starts with an underscore or letter and contains only letters, numbers, and underscores" (source). This means that when your program reads the and, it can read it as the identifier and or the keyword and.

It looks to me like you can fix this by declaring your operators to be punctuation with the following line:

MarkPunctuation("imp", "and", "or", "not")

这篇关于实现使用反讽一个前缀符号表达式解析器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！