请解析此aLL1en语言
背景
由于一些编码过程中的不幸事故，你现在被传送并被困在一个外星上。你真的希望当地人会有所帮助，并指出如何回家的总体方向，但在试图与他们交谈之前，你想要解读他们的语言。幸运的是，外星人似乎已经预料到了这一点，并且在你被传送的地方附近显示了他们语言的语法。
您的任务
您的工作是编写一个LL(1)解析器，该解析器可以确定特定字符串是否属于指定的语法，并返回解析过程中使用的规则。您的手指有点紧张，因为传送，所以您希望用尽可能少的字符来编码这个解析器。
另外，由于一些奇怪的原因，那里有免费的wifi，但只有维基百科可用，所以如果您需要帮助，可以检查如何解析一个LL(1)语法，以及如何为它创建解析表。
输入
输入的第一行是需要解析的字符串。下面的行都将包括可用的语法规则，其中第一个字符是规则的左边，其余的是规则的右侧。
示例输入：
(a+a)
SF
S(S+F)
Fa它描述了您必须确定( a + a )是否是下列语法的一部分：
S → F
S → ( S + F )
F → a关于投入的说明：
- 语法可能包含空(epsilon)规则，在这里右边是空的。
- 所有终端和非终端只占用一个字符。
- 终端的特征如下：
abcdefghijlkmnopqrstuvwxyz+-/*^%=()[]{} - 非终端的字符如下：
ABCDEFGHIJKLMNOPQRSTUVWXYZ - 启动的非终端总是
S - 您可以假设输入中的语法始终是适当的LL(1)语法。
- 后面的换行符可能出现，也可能不在，这是你的选择。
输出
输出应该包含字符串是否是语法的一部分，如果是的话，还应该包含用于解析的规则。
上面输入的示例输出：
true
S(S+F)
SF
Fa
Fa只要输出返回所需的所有信息，就允许对输出进行更改。例如，以下输出也被认为是可接受的：1 [2,1,3,3] (1，因为字符串被接受了，那么[2,1,3,3]是作为数组使用的规则，其中每个元素表示从一个开始的输入中的规则索引)
评分
您必须编写完整的程序(从STDIN读取)或函数(从字符串读取)。可以对STDOUT执行输出，也可以以适当的方式(如Pair<bool,int[]>)从函数返回。
得分是程序的字节计数，有以下惩罚：
- 将10添加到字节计数并将其平方，以防使用所选语言的内置LL(1)解析器
- 将100添加到字节计数并将其平方，以防使用内置的LL(2+)、LR(1)、LR、SLR或任何其他比LL(1)更高级的解析器。
- 虽然它们可能不会比LL(1)更高级，但是如果您使用的正则表达式特性不被认为是常规语法的一部分，请使用前面的惩罚。
(这些惩罚是适用的，因为传送者把这些内置的函数搞砸了，你必须先神奇地修复它们)
注：
普通正则表达式是允许的，不算在惩罚中，除非您使用高级regexp特性，使表达式不再是规则语法。此外，使用内置的LR(0)解析器也可以(但可能没有多大帮助)
最低分获胜.
如果您的语言不是基于字符的，请为您的语言使用适当的度量，然后对结果进行惩罚。标准漏洞适用，但解决方案的语言更新后，张贴后，允许您添加适当的免责声明到您的帖子。
示例
在：
(a+a)
SF
S(S+F)
FaOut：1 [2,1,3,3]
在：
(aa)
SF
S(S+F)
FaOut：0
在：
a*(a+a)
STE
E+TE
E
TFU
U*FU
U
F(S)
FaOut：1 [1,4,8,5,7,1,4,8,6,2,4,8,6,3,6,3]
在：
aaabbb
SaA
AaAb
AbOut：1 [1,2,2,3]
在：
aabbb
SaA
AaAb
AbOut：0
在：
aaabb
SaA
AaAb
AbOut：0
回答 1
Code Golf用户
发布于 2021-07-25 16:26:00
JavaScript (ES6)，177个字节
177个看起来像LL1旋转了177°，所以我停止打高尔夫球。
s=>(f=(x,i)=>x<"A"||x>"Z"?v=s[i]==x&&[i+1,x]:s.split`
`.some((r,a,j)=>v=r[0]==x&&[j=i,a=[a],...r].slice(3).every(y=>f(y,j)&&a.push(([j]=v)[1]))&&[j,a]))("S",0)&&s[v[0]]==0&&v[1]如果字符串不匹配，则输出false，否则输出规则索引和终端的嵌套数组：
[2,"(",[1,[3,"a"]],"+",[3,"a"],")"]Ungolfed
str =>
(applyRule = (ruleName, index) =>
ruleName < "A" || ruleName > "Z"
? result = str[index] == ruleName && [index + 1, ruleName]
: str.split("\n").some(
(rule, appliedRules, jndex) => result =
rule[0] == ruleName &&
(
jndex = index,
appliedRules = [appliedRules],
[...rule].slice(1).every(char =>
applyRule(char, jndex)
&& appliedRules.push(([jndex] = result)[1])
)
&& [jndex, appliedRules]
)
)
)("S", 0)
&& str[result[0]] == 0 // "\n" == 0
&& result[1]function main(input) {
const [str, ...rules] = input.split("\n")
const result = applyRule("S", 0)
if(result && result[0] === str.length)
return result[1]
function applyRule(ruleName, index) {
if (ruleName === ruleName.toLowerCase())
return str[index] === ruleName ? [index + 1, ruleName] : null
main: for (const [ruleIndex, rule] of rules.entries()) {
if (!rule.startsWith(ruleName))
continue
let curIndex = index
let appliedRules = [ruleIndex + 1]
for (const char of rule.slice(1)) {
let result = applyRule(char, curIndex)
if (!result) continue main
curIndex = result[0]
appliedRules.push(result[1])
}
return [curIndex, appliedRules]
}
return null
}
}https://codegolf.stackexchange.com/questions/67033
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号