|
t*******r
发帖数: 22634 | 2 另外你等等，我马上发一新贴， 里面把 yacc 段落改写成递归 C伪码，
码工么，小菜一碟。 |
|
b*********z
发帖数: 26 | 3 哇，memorial day长假出去玩回来想起这个帖子，楼又高了许多，代码都出来了，我等
码工真欢乐！
以前上mitbbs，我只潜水。不过，我承认这次我也灌了许多水，试图引起LZ思考哪里错
了。
好吧，楼很高了，我就总结一下我的发言吧。
首先说，素数的定义是大于1除了自己和1不能被其他自然数整除的自然数。
我把一楼的证明拷贝过来，并在下面一步一步举个简单的例子说明哪步错了。
－－－－－－－－－－
假设素数只有有限个, 记为 p_1,p_2,...,p_k
（假设素数只有有限个，为2，3，5，7，11，13.这些都是符合定义的素数，而且在13
以下没有遗漏，p_k就是13）
考察 N = p_1*p_2*...*p_k + 1
（考察N＝2*3*5*7*11*13＋1=30031）
可知: 对于任意i = 1,2,3,...,k, p_i 不能整除 N
（2，3，5，7，11，13都不能整除N。这句话是对的）
由素数的定义:
a是素数 <=> a是大于1的自然数, 且a不被任何小于a的素数整除
可知: N是素数
（这是错的。30031=59*509，N不是素数）
这与素数只有p_1,p_... 阅读全帖 |
|
t*******r
发帖数: 22634 | 4 汉语英语啥的，对俺码工太难了。还不如俺上面直接看着 yacc 人肉翻译成 C伪码。。。
LOL |
|
t*******r
发帖数: 22634 | 5 其实就有点像罗素悖论，你俩看同一个自然语言，结果看到是不同的意思。
这不奇怪，我一开始看楼主的，也没看明白。也争了一大通。不过后来发现
那是古典数学语言。码工多用现代数学集合论图论正则语言，或者类似正则
语言写法的东东，导致看古典数学转不过弯来。
楼主的证明其实没错，但是用到了素数的递归定义，实际上我认为是个
trivial 的证明。（由素数递归定义可以容易直接证明无限性，不需要
反证或归谬）。
老实说素数的递归定义并不显而易见，我觉得非码工用自然语言理解，很可能是
似懂非懂。说实话我一开始其实也理解有偏差，导致一开始写的那个 yacc/c
伪码里，把 if and only if 里的 only if 判断条件写错了。其实那个
不是笔误，是理解错误。但写正则语法就是有这个好处，写出来，testcase
跑对，也就基本理解对了。 |
|
t*******r
发帖数: 22634 | 6 具体而言，这里的 set，用自然语言描述，是“前N个完整连续素数的集合”。
（但是，again，正则文法里，这个自然语言的描述，只能用来帮助理解。
权威的定义来自那段伪码 code。）
第二个问题，是不是同一 set？容我这么唐：
在变量赋值的时候，你开始写了个 “a = 2”，后面又写了一句 “a = 5”。
你说这两个 a 是不是同一个 a？
那我进一步说，我写了一个 token，意义是“单个自然数”。开始的时候这个 token
是 “50”，后来这个 token 被改成 “100”，那这个 token 还是不是
“单个自然数”。
那我再进一步说，我写了个 token，意义是“前N个连续自然数”。开始的时候
这个 token 是 ( 1 , 2 )，后来这个这个 token 变成 （1, 2, 3, 4, 5)。
那这个 token 是不是还是“前N个连续自然数”？
那我再再进一步说，你要是写了个 “a = a + 1”，你说这两 a 是不是同一个 a？
那我要是写个 yacc reduce “token : token 1”，把 token reduce 成
token 和一... 阅读全帖 |
|
t*******r
发帖数: 22634 | 7 我以为我们是在把自然语言定义翻成 formal logic，
用 yacc伪码 或者 C伪码 。。。 |
|
l*3
发帖数: 2279 | 8 请求: 不要再跟我谈伪代码了, 我真的不懂伪代码, 认输!
我懂C代码, 但不懂伪代码, 尤其是我连是什么东西都不知道的 "yacc伪代码".
你的任何解释, 都可以是基于汉语的, 请不要在证明中说到 "伪代码" 相关的东西.
你用汉语解释一下你定义中的 "生成" 是一个什么样的操作.
我现在无法判断你说的是不是有道理. 因为你的每一句话都要往上回溯好几楼, 而且要
归结到最开始的 "伪代码" 情形. 我无能力处理这种情况.
-------
请你直接用汉语, 重新表述一下, 如何不用反证法证明 "素数有无穷个".
谢谢啦! |
|
l*3
发帖数: 2279 | 9 请你认识到 "我作为一个自然人" 的局限性.
对于 "yacc" 神马的, 我表示认输了!
PS, 以上非调侃..
你之前问过我一句 "看糊涂了没?", 我现在明确而大方地回应你:
糊涂了~ |
|
t*******r
发帖数: 22634 | 10 第三个问题，昨晚你问的，能不能用自然语言表达。我觉得应该这么说。
如果要用自然语言表达，我就必须在白板上画一张“语法生成树”，然后
再讨论。这样我不需要用任何“yacc伪码”之类的表述，可以直接用
“产生 token”，“token 加”，“token 减” 等等自然语言（或者
不喜欢 token 这个词，改成集合好了，反正 formal logic 么，
用啥词关系不大）。
但是 BBS 上不行，没白板，用 text 画 graph/tree 要累昏。。。
原因，again，个人认为是大脑思维方式的
spatial(symbol) vs sequential(verbal)。 |
|
t*******r
发帖数: 22634 | 11 另外，理论上，Yacc 可以用来写 C 编译器的语法分析阶段。
而且 ISO/IEC/IEEE 的 C 标准文本的语法部分是用 BNF
（Backus–Naur Form）写的。
没这个高楼前没体会到 formal logic 在码工界如此深入
人心 + 潜移默化。。。 |
|
k******a
发帖数: 2436 | 12 I thought YACC can only build LR parsers but I could be wrong |
|
t*******r
发帖数: 22634 | 13 这个高楼，还是加深俺对码工所用实用数学的体会（或者说是偏见也成）：
中学数学里欧几里德的数学思想，虽然精巧，但对码工而言，帮助不大。
个人觉得对码工所用现代数学思想最有帮助的，恰恰是那些看起来
傻大笨粗的东东，能想起来的是：
数学归纳法
解析几何
泰勒展开
傅立叶变换
第一个编程语言
（过去是 Pascal 或 C，现在可能是 Java）
计算机图论
YACC 和 formal language
乱序执行的超级标量流水线结构 |
|
l*****8
发帖数: 16949 | 14 您老人家错太多了啊
正则语法是regular expression吧？yacc对应的是上下文无关文法（的一个子集）。程
序设计语言对应的是上下文相关文法。无论什么文法，定义出来的程序只能计算可计算
函数。可计算函数时数学函数的一个极小的子集。
不要拿计算机的东西来随便往数学上套，这两个差别太大了。 |
|
t*******r
发帖数: 22634 | 15 你说的没错，俺数学的确不行，所以做码工正好。。。 :-)
至于计算机中文词汇，我承认是不行。不过这不怪我，是 I63 坚持要我敲
中文词汇的。再说了，灌水主要是开心，一个一个查翻译太费事了。不过
以后俺术语少用中文，省得落下蛊惑大众的骂名。。。
另外 YACC 实际上是根据类似 BNF 的定义格式自动生成 parser 的程序，
生成的是 LALR parser，如果我没有记错的话。。。 |
|
t*******r
发帖数: 22634 | 16 俺是 Algorithm-Depot 门口的老莫，主要给老板干体力活。。。
十多年前曾经用 YACC 写过一个简单的 parser，不过那个语法很简单。
后来没再写过 parser，也忘得差不多了。
复杂的文法可以写成 tree，其实不少 tree 算法也可以看成是某种
文法，不过大伙儿一般不从这个角度看。。。
free
集。 |
|
l*****8
发帖数: 16949 | 17 从定义上说，Formal Language就是字符串的集合。程序设计语言就是一种formal
language.比如Java语言就包含了所有可以合法编译运行的Java程序（一个程序可以看
成一个字符串）。
regular expression不是formal language,是定义formal language的一种办法。它生
成的语言叫做正规（还是叫正则？英文叫regular language）语言。Regular
languages还可以用DFA(Deterministic finite automata), 或者NFA(non-
deterministic finite automata)生成。还有一种叫做linear grammar也能生成这类语
言。
另一类语言叫做context-free language(CFL). 这类语言可以由context-free grammar
生成，也能由non-deterministic pushdown automata生成。CFL有一个子类叫做DCFL(
deterministic context-free language),这类语言... 阅读全帖 |
|
s***e
发帖数: 403 | 18 看出我是谁的给点面子，就别说破了。如果哪位师兄师姐师弟师妹有个什么软件公司的
码工内推，不妨给我试试，应该不会丢大家的脸。
干了几年，老板想让我拿硕士毕业，貌似不是很想给我博士学位。实验室里做的东西基
本上不适合找工作，所以现在求CS方面的机会。
技能：6+年C/C++经验，熟悉C++11，熟悉stl/boost，熟悉过程式/面向对象/模板元风
格编程，了解lambda编程，基本上可以短期轻松上手任何不是LISP系列的语言。了解
windows下的MFC开发，熟悉qt4库，熟悉linux系统和shell编程，熟悉基本算法和数据
结构，熟悉常用设计模式。有独立开发经验。有并行开发（pthread, openmp, intel
tbb）和性能优化（Vtune)的经验。能看懂汇编，但是自己写就不行了。有建模经验。
了解计算机基本架构（差不多是看完CSAPP那本书的水平）。了解一些操作系统，网络
方面的知识。还有一些相对垃圾的技能比如会用lex/yacc，会一点ruby，会用blas和
lapack，会打星际2……
地方不限，北美除了犯罪率高的地方以外，随便到哪里都可以。要求工资能养的起自己
... 阅读全帖 |
|
|
k****e
发帖数: 100 | 20 手头上有个软件，不过不支持表达式，比如对于：
a:=4*5
b:=2+a
t: property1=b, property2=a
只能将b和a计算出来，然后写：
t: property1=22, property2=20
我想扩展一下这个程序，模模糊糊感觉lex/yacc（没用过）或者python 的eval（用它
写
个模块，做表达式计算，然后替代）能帮上点忙。各位有什么建议么？ |
|
|
I**********s
发帖数: 441 | 22 javaCC用在java平台上是不错. 说到LR parser, 并没有流行的版本. 常用的yacc,
bison, byacc等都是LALR(1). LR(1)的优点在于可以分析所有context free的语法, 这
一点LALR(1)做不到. 而LL的语法也可以转换成LR(1). Knuth的原LR(1)算法长期一直被
认为速度太慢, 产生的parsing table太大. 即便现在, 用Knuth原算法实现的LR(1)
parser generator也常常需要很长时间才能完成运算. 比如我听说一个C++
implementation对于一个about 120 tokens, 350 production的语法, 要20分钟才能得
到结果. 另外一个implementation(in Python?), 作者称对大约100 tokens, 500
productions的语法, "I let it run for nearly three days, and it was far from
finishing, but using nearly 16GB of memory" |
|
I**********s
发帖数: 441 | 23 "Specially take care of" can be a pain sometimes when you need to modify the
grammar, and you may not be sure the modified grammar is the same one as
before. Indeed a lot of things can be solved by precedence and other
conflict resolving methods. yacc/bison and now javacc can be used for most
compiler development tasks. But still there are people puzzled by the "
mysterious reduce/reduce conflict" and hope to find a LR(1) solution. Anyway
, I hope what I did can be an answer to this. |
|
d****g
发帖数: 1049 | 24 借你的牛刀杀只小鸡:)
我正在写一个处理格式文本的程序。想用flex,感觉是用不到yacc.
文件格式很简单，就是:
关键词：数据
但是文本里有不同数据块，比如：
类型: 联系方式
姓名：xxx
地址：xxx
类型：产品
名称: xxx
型号: xxx
类型：运动
名称：xxx
类别：xxx
我觉得用flex就足够了，因为结构比较简单。
我看了看flex的说明，有一点不知道怎么弄。
就是我拿到关键词以后怎么再拿到数据？
我应该在下面的规则里面加一个什么规则？
我现在是用".", 然后把所有不和关键字匹配
的字符全送到一个字串，可是觉得这么做很慢，
而且好像也很笨:)
%%
{keyword} {printf("%s\n", yytext);}
. {strcat(data,yytext);}
%% |
|
g*****n
发帖数: 420 | 25 Antlr 可以生成C的代码，而且生成的代码比较像人写的，比较好调试。lex和yacc这种
东西生成的代码比较像天书 |
|
p****2
发帖数: 387 | 26 请教一个问题：请问用Bison/Yacc可以实现把Object Code加到源程序中。
譬如，Source1能引用object2.o中的函数. |
|
p****2
发帖数: 387 | 27 what if the included function/file is also a source/object generated by
yacc/bison? thanks!
"#include"s in |
|
D*****r
发帖数: 6791 | 28 你得先把分类弄清楚，编译原理是理论课，操作系统其实是系统课，软件工程是编程/
开发课。每门的学法不一样。
编译的正则语言、上下文无关语言等等就是数学（别让数学系的人听见），跟离散数学
、计算理论里的东西一脉相承，你就当数学来学，看书、做题，没问题。
编译器设计上前端的scanner，parser利用这些理论知识，已经有现成的lex,yacc工具
了，都是成型的东西，主要是后端代码生成还需要优化啥的。我也不懂就随便一说……
编译原理和操作系统、软件工程都是核心好课，不亚于数据结构和算法，甚至更重要。
好好看书(权威、经典的），多看UCB，mit open courseware，stanford等学校的课程
录像\大纲作业，最好能自己搞点pet project玩起来。
你现在思路得转一下，理论课靠看书做题，系统和编程开发课都得靠实践（所谓做题没
用）你在linux下面练习一下系统编程，去linux kernel的开发现场（在git上）参观一
下，到软件公司实习一下，就更能体会这些课程的性质了。 |
|
g****v
发帖数: 971 | 29 最近需要分析优化c或是c++写的文件，准备用lex&yacc来做这个事，但是发现没有现成
的bnf文
件。请问大家谁知道哪里可以找到bnf for c or c++？
或是说有没有轻量级的parser for c or c++？
谢谢了，
5个包子 |
|
z***y
发帖数: 42 | 30 javacc. (like LEX/YACC)
They have C grammar available. |
|
c*****t
发帖数: 1879 | 31 I have to test outputs against standard outputs. My code is a
compiler-compiler (i.e. lex/yacc like).
Even worse, I might have to test the if the outputted java code
which in turn gets compiled produce the right outputs for given
inputs.
One of the reason why I needed to test is because a slight tweak
may not be apparent in correctness, and only through tests to
tell. A single generated piece of code itself can work in some
cases, but not all cases...
I am having a major headache :( ATM, I ca |
|
c*****t
发帖数: 1879 | 32 ... 你去看看那个 lex yacc tutorial 。有简单的 +-*/ 计算。。。 |
|
c*****t
发帖数: 1879 | 33 Trivial.
Learn to use lex / yacc. Then you can use CookCC easily write one
under 10 minutes. |
|
k****u
发帖数: 133 | 34 he may have to spend 10 days on lex/yacc before that 10 min, :-) |
|
X******w
发帖数: 159 | 35 真是惭愧，刚开始学，还没有接触到lex/yacc. 多谢 |
|
g*****g
发帖数: 34805 | 36 It takes 10 min to code one without knowing lex/yacc. |
|
|
g****g
发帖数: 1828 | 38 AWK是一种优良的文本处理工具，Linux及Unix环境中现有的功能最强大的数据处理引擎
之一。这种编程及数据操作语言（其名称得自于它的创始人 阿尔佛雷德·艾侯 、
Peter Weinberger 和 Brian Kernighan 姓氏的首个字母）的最大功能取决于一个人所
拥有的知识。 AWK 提供了极其强大的功能：可以进行正则表达式的匹配，样式装入、
流控制、数学运算符、进程控制语句甚至于内置的变量和函数。它具备了一个完整的语
言所应具有的几乎所有精美特性。实际上 AWK 的确拥有自己的语言： AWK 程序设计语
言， 三位创建者已将它正式定义为“样式扫描和处理语言”。它允许您创建简短的程
序，这些程序读取输入文件、为数据排序、处理数据、对输入执行计算以及生成报表，
还有无数其他的功能。gawk 是 AWK 的 GNU 版本。
最简单地说，AWK 是一种用于处理文本的编程语言工具。AWK 在很多方面类似于 Unix
shell 编程语言，尽管 AWK 具有完全属于其本身的语法。它的设计思想来源于
SNOBOL4 、sed 、Marc Rochkind设计的有效性语言、语言工具 y... 阅读全帖 |
|
|
g*********s
发帖数: 1782 | 40 用的bison。
google了一下，好像是在执行bison foo.y时加--debug选项，再在调用yyparse()之前
加上这两个语句：extern int yydebug; yydebug=1; 说是这样执行parser后就会有个
foo.output文件给出token parse的信息。
试了一下，不灵啊。还有说法要加--verbose选项，定义宏#define YYDEBUG 1等等，谁
知道到底怎么回事啊？ |
|
k****e
发帖数: 100 | 41 编译的时候有一个 -t -d 什么的选项，看一下man吧 |
|
|
t****t
发帖数: 6806 | 43 info bison
第8章 (debugging) |
|
|
w***g
发帖数: 5958 | 45 I think boost has a parser library.
60 |
|
c*****t
发帖数: 1879 | 46 所有在这里的 test case 都是测试过的（不过 parser 部分还在 svn 里，
我现在还差将 compressed table 放进 code generator）。
http://code.google.com/p/cookcc/source/browse/trunk/tests/
code generator 现在只有 Java 。其实弄 C/C++ 也不是太难（毕竟是
template approach）。
现在用的是 xml 输入。主要是 yacc/lex 的输入文件其实很复杂。手工写
parser 太困难。至于自动 generate，俺不正在写嘛。
至于 mix 代码和 grammar 。我有个想法，不适合 C/C++，但是很适合
Java / C# / Python 。这样可以直接利用现成的 Java/C#/Python editor
（同时该 editor 的功能，比如 refactoring，context sensitive help
等）。我已经手工推出个 prototype，就差 implementation 。 |
|
c*****t
发帖数: 1879 | 47 Look at this Lex/Yacc tutorial:
http://epaperpress.com/lexandyacc/
It apparently has a fairly good integer based math calculation
interpreter (including variable decl and loop etc).
Some slight modifications and you can have it to suit your need. |
|
w***g
发帖数: 5958 | 48 比较古老的有lex, yacc, gperf，目前比较时兴C++ TML。 不知到还有别的什么语言。 |
|
g*********s
发帖数: 1782 | 49 有这么一个问题：
for (int i = 0; i < n; i ++) {
yyin = fopen(f[i], "r");
try {
yyparse();
}
catch ...
}
这里.y里重定义了yyerror，有语法错就throw一个exception。
现在的问题是，如果f[1]有parse error，之后的f[2]，f[3]等还是从f[1]原来的yylex
buffer里拿token，而不是自己的文件里。
怎么才能在yyerror()里，throw exception之前reset yylex buffer呢？放狗搜了一下
，有个YY_FLUSH_BUFFER的macro，但这个是只在.l里可见的，而.y里不可见。
另外现在还有人用flex/bison吗？很麻烦啊。 |
|
