我必须计算以下语法的第一组和第二组:
S -> ABC
A -> a | Cb | 1
B -> c | dA | 1
C -> e | f
然而,我不完全确定我是否了解如何做到这一点。根据我的理解,我得到了以下计算:
FIRST(S)= {a, e, f, b, c, d}
FIRST(A)= {a, e, f, 1}
FIRST(B)= {c, d, a, e, f, b, 1}
FIRST(C)= {e, f}
FOLLOW(S)= {$}
FOLLOW(A)= {c, d, a, e, f, b}
FOLLOW(B)= {e, f}
FOLLOW(C)= {$
这里S是非终端开始符号;A,B,C是非终端符号;x,y是终端符号。
S → A B A C | A C A B
A → A x | A y
B → B x x | B y y
C → x y | y x
看过视频后,我理解了在生产规则中消除左递归的简单示例,如
S → a S a
S → b S b
S → ε
但我不明白如何消除上述规则中的左递归。有人能向我解释或指出解释的方向吗?
在查找以下集合时,规则(如A->aA )可能导致无限递归。有什么编码技术可以避免吗?
请注意,上面的示例只是一个示例,在实践中,这样的递归也可能间接发生。
下面是我的示例C代码,用于查找以下集合。语法存储为链表数组。请告诉我代码在任何时候是否不清楚.
set findFollowSet(char nonTerminal[], Grammar G, hashTable2 h) //later assume that all first sets are already in the hashtable.
{
LINK temp1 = find2(h, nonTerminal);
我有一个语法,并想证明它不是LL(1)中的:
S->SA|A
A->a
由于它是一个左递归语法,为了找到第一个和后续的集合,我消除了左递归,得到了:
S->AS'
S'->AS'|Empty
A->a
first of A={a} follow of S={$}
first of s'={a,ε} follow of S'={$}
first of S={a} follow of A={a,$}
但是,当我填写解析表时,我没有得到任何带有两个条目的单元格。那么,如何证明给定的语法不在LL(1)中?
我们得到了一个API -
removeAndAppend(val)
//Removes val and appends it to the given collection
我们需要使用这个API对集合进行排序。
我知道我可以通过-
for i <- N to 1
extract max //in O(n)
removeAndAppend.. //Consider this O(1)
这是二次型..。
问题是我能做得比这更好吗?
编辑:我们可以像-比较法(val1,val2)那样对集合进行读取操作。
我有一个名为x的字符串数组,它包含“男孩”或“女孩”。然后我想在不改变x的顺序的情况下创建N个组,每个组必须至少有两个字符串,并且组的第一个成员和最后一个成员必须是相同的字符串(“男孩”或“女孩”)。返回创建组的方法的数量。
示例:
String[] x = {"Boy", "Boy", "Girl", "Boy", "Girl", "Girl", "Boy", "Boy"}; // Can be any length
int N = 3; // N <= x.
def getAllSubsets(lst):
"""
lst: A list
Returns the powerset of lst, i.e. a list of all the possible subsets of lst
"""
if not lst:
return []
withFirst = [[lst[0]] + rest for rest in getAllSubsets(lst[1:])]
withoutFirst = getAllSubsets
我必须计算以下语法的第一组和第二组:
A -> B C
B -> A x | x
C -> y C | y
根据我的理解,我得到了以下计算:
首先,我们删除左递归。
A -> B C
B -> x B'
B' -> C x B' | ε
C -> y C | y
Follow (A) = {$}
但在书中,Follow (A) = {x,$}的答案
为什么?他们没有删除左递归吗?
我为一个解析器编写了以下代码,该解析器接受来自父类的链表参数。在我输入表达式之后,它抛出了一个堆栈溢出错误。
我从Swing类中的jTextField传递输入表达式,然后将布尔结果返回给同一个类中的jLabel。堆栈溢出错误的原因可能是什么?请帮帮忙,谢谢!
示例输入:
1+2+3
(1+2)/(3+4)
import java.util.LinkedList;
class Token {
public static final int PLUS_MINUS = 0;
public static final int MULTIPLY_DIVIDE = 1;
publi
我有以下处理数学和逻辑表达式的语法: A ==> B A'
A' ==> | B A'
A' ==> epsilon
B ==> C B'
B' ==> ^ C B'
B' ==> epsilon
C ==> D C'
C' ==> & D C'
C' ==> epsilon
D ==> E D'
D' ==> << E D' | >> E D'
D' =
我有一个关于我用C编写的解析器的问题,它应该使用左递归(为操作符提供左结合性),然后返回后缀表示法的表达式。特别适用于我的Expr和Term规则。目前我遇到了一个问题,我认为这不会发生。下面是我的语法:
extern int yylex(); /* The next token function. */
extern char *yytext; /* The matched token text. */
extern int yyleng; /* The token text length. */
void yyerror(char *s);
#define YYSTYPE long /* 6
此查询返回使用变量定义的日期范围之间的所有日期,并且结果集是31个不同的值。但是,递归CTE的工作方式是第一个查询只执行一次,第二个查询处理之前创建的结果集。所以,看起来会有重复,但它返回了不同的结果集。CTE是在内部应用DISTINCT子句还是其他什么?如何获得不同的值?
DECLARE
@DateFrom DATE = '20130101' ,
@DateTo DATE = '20130131'
WITH Days
AS ( SELECT CAST(@DateFrom AS DATETIME) AS dt
UNION ALL
这是我最近遇到的一个面试问题。您在party.Each中有G个来宾(编号从1到G),它有一个长度为G的首选项列表,该列表表示他与他人交谈的首选项。例如,如果来宾1的偏好列表是N Y N N Y(假设有5个来宾),则来宾1有兴趣与2或5交谈,而不与其他人交谈。
假设
a)每个来宾只能与另一个来宾交谈
b)如果a有兴趣与b交谈,那么b也有兴趣与a交谈。
给出一个客人矩阵和他们的偏好,给出可以保持联系的最大配对数量。
Let G = 5;
偏好矩阵是
N Y N N N
Y N Y Y Y
N Y N N N
N Y N N N
N Y N N N
正如我们可以观察到的,每个人都有兴趣与Guest
这是一个我想写的函数,但我无法这样做。即使你不能/不能给出一个解决方案,我也会非常感谢你的建议。例如,我知道整数和有序集分割的有序表示之间存在相关性,但这本身并不能帮助我找到解决方案。下面是我需要的函数的描述:
任务
创建一个高效的*函数
List<int[]> createOrderedPartitions(int n_1, int n_2,..., int n_k)
这将返回集合{0,...,n_1+n_2+...+n_k-1}的所有集合部分的数组列表,以大小为n_1,n_2,...,n_k (按此顺序)的number of arguments块(例如n_1=2, n_2=1,
假设我有这样的语法:
S -> A C x | u B A
A -> z A y | S u | ε
B -> C x | y B u
C -> B w B | w A
这个语法显然不是LL(1),我可以在构造解析表时找到它。但是,有没有什么方法可以证明这个语法不是LL(1),而不使用经典的方法,也就是不构造解析表或发现任何冲突?
另外,如何将此语法转换为LL(1)?我想我必须同时使用epsilon派生消元法和左递归消元法,但这有点棘手,我试过很多次,都不能把它转换成LL(1)。
提前谢谢你。