相关疑难解决方法(0)

词法分析器和解析器在理论上真的有那么不同吗？

讨厌正则表达式似乎很时髦:编码恐怖,另一篇博客文章.

然而,流行的基于乐兴的工具:pygments,geshi或者美化,都使用正则表达式.他们好像有什么东西......

什么时候足够兴奋,什么时候需要EBNF？

有没有人使用这些词法分析器生成的令牌与野牛或antlr解析器生成器？

它们是由编译过程的不同阶段产生的吗？或者它们只是同一个东西的不同名称？

我在编译器设计书中找到了这两个术语,我想知道每个术语代表什么,以及它们是如何不同的.

我在互联网上搜索,发现解析树也称为具体语法树(CST).

我想从一个令牌列表中构造一个AST.我正在编写脚本语言,我已经完成了词法分析部分,但我不知道如何创建AST.所以问题是,我该怎么做这样的事情:

WORD, int
WORD, x
SYMBOL, =
NUMBER, 5
SYMBOL, ;

并将其转换为抽象语法树？最好,我想在没有像ANTLR之类的库那样的情况下这样做,我宁愿自己尝试从头开始.但是,如果这是一项非常复杂的任务,我不介意使用库:)谢谢

我目前正在构建一个用PHP编写的PHP解析器,因为在我之前的问题中没有出现现有的解析器.该分析器本身运作得相当好.

现在很明显,解析器本身没什么用(除了静态分析).我想将转换应用于AST,然后将其编译回源代码.应用转换不是一个问题,普通的访客模式应该这样做.

我目前的问题是如何将AST编译回源代码.我看到基本上有两种可能性:

1. 使用某种预定义方案编译代码
2. 保留原始代码的格式并仅在已更改的节点上应用1.

现在我想专注于1.因为2.似乎很难完成(但如果你有相关的提示,我想听听它们).

但我不确定哪种设计模式可用于编译代码.我看到实现这一点的最简单方法是->compile向所有节点添加一个方法.我在这里看到的缺点是,更改生成的输出的格式非常困难.人们需要更改节点本身才能做到这一点.因此,我正在寻找一个不同的解决方案.

我听说访客模式也可以用于此,但我无法想象它应该如何工作.据我了解访问者模式,你有一些NodeTraverser在所有节点上递归迭代并调用一个->visit方法Visitor.对于节点操作来说这听起来非常有前景,其中该Visitor->visit方法可以简单地更改它传递的Node,但我不知道它如何用于编译.一个显而易见的想法是将节点树从叶子迭代到根,并用源代码替换访问的节点.但这在某种程度上似乎不是一个非常干净的解决方案？

我正在阅读有关AST(抽象语法树)的内容,但我看到的所有示例都使用了以下表达式:

a + b * c 

哪个可以用类似lispy的语法表示为:

(+ a (* b c) )

这相当于:

  +
 / \
a   * 
   / \
  b   c

我的问题是OOPL中一个类的AST会是什么样子？

我天真的尝试是为了这个Java代码:

 class Person { 
     String name;
     int    age;
     public String toString() { 
        return "name";
     }
 }

方法是:

;Hand written
(classDeclaration Person 
     (varDeclaration String name)
     (varDeclaration int    age )
     (funcDeclaration String toString 
           (return "name")
     )
 )

但我不太确定我对真正的AST代表有多近或多远.

这取决于我选择的语言.需要多少细节？这些"xyzDeclaraction"是否需要或可能如下:

 (Person (String name) (int age))

在哪里可以看到实际编程语言的"真实"表示以了解更多信息.

为了更好地理解C++语言和语法的一些细节,我希望能够编写一个小的C++程序,并查看编译器从中生成的AST.

看起来clang过去有这个功能(-emit-asm),但它已经删除了.

今天有一个简单的方法吗？

我正在学习编写一种编程语言的解释器,我读过有关抽象语法树的文章.我知道它们是什么,但我看不出它们的用途.

为什么AST有用？

摘要问题描述:

我看到它的方式,unparsing意味着从AST创建一个令牌流,当再次解析时产生一个相等的AST.

所以 parse(unparse(AST)) = AST持有.

这等于找到一个有效的解析树,它将生成相同的AST.

该语言由使用eBNF变体的无上下文 S属性语法描述.

因此,解析者必须通过所有语法约束所包含的遍历节点找到有效的"路径".这基本上意味着找到AST节点到语法生成规则的有效分配.这通常是一个约束满足问题(CSP),可以通过回溯 O(exp(n))来解决,如解析.

幸运的是,对于解析,这可以使用GLR(或更好地限制语法)在O(n³)中完成.因为AST结构非常接近语法生成规则结构,所以我真的很惊讶看到运行时比解析更糟糕的实现:XText使用ANTLR进行解析和回溯以进行解析.

问题

1. 是一个上下文无关的S属性语法解析器和解析器需要共享的所有东西,还是有进一步的约束,例如解析技术/解析器实现？
2. 我觉得这个问题一般不是O(exp(n)) - 有些天才可以帮助我吗？
3. 这基本上是一个上下文敏感的语法吗？

例1:

Area    returns AnyObject   -> Pedestrian | Highway
Highway returns AnyObject   -> "Foo" Car
Pedestrian  returns AnyObject   -> "Bar" Bike
Car     returns Vehicle     -> anyObjectInstance.name="Car"
Bike    returns Vehicle     -> anyObjectInstance.name="Bike" 

所以,如果我有一个AST包含

AnyObject -> AnyObject -> Vehicle [name="Car"] 我知道root可以是Area,我可以解决它

Area    -> Highway  -> Car

因此(公路|行人)决定取决于子树决策.当一片叶子乍一看是几种类型中的一种时,问题会变得更糟,但必须是特定的一种,以便稍后形成有效路径. …

在查看可能的工具后,我需要分析Objective-C静态代码,主要是AST,我发现LLVM中的Clang工具可以转储AST,所以我使用终端使用这个命令测试它:

clang -cc1 -ast-dump ~/SomeTest.m

但我收到这个错误:

In file included from /Users/myusername/SomeTest.m:9:
/Users/myusername/SomeTest.h:9:9: fatal error: 'UIKit/UIKit.h' file not found
#import <UIKit/UIKit.h>
        ^
typedef __int128_t __int128_t;
typedef __uint128_t __uint128_t;
typedef SEL *SEL;
typedef id id;
typedef Class *Class;
struct __va_list_tag {
    unsigned int gp_offset;
    unsigned int fp_offset;
    void *overflow_arg_area;
    void *reg_save_area;
};
typedef struct __va_list_tag __va_list_tag;
typedef __va_list_tag __builtin_va_list[1];
@interface just4testViewController@end
@implementation just4testViewController
- (void) dealloc (CompoundStmt 0x7f86b183b110 </Users/myusername/SomeTest.m:14:1, line:16:1>)


- (void) didReceiveMemoryWarning (CompoundStmt 0x7f86b183b2a0 </Users/myusername/SomeTest.m:19:1, line:24:1>)


- (void) viewDidUnload (CompoundStmt 0x7f86b183b430 …