Please parse this aLL1en language

Question

Background

Due to some unfortunate accident during coding you are now teleported and stranded on an alien planet. You really hope that the locals will be helpful and point to the general direction of how to get home, but before trying to talk to them you want to decipher their language. Fortunately it looks like the aliens were expecting this, and are actually displaying the grammar of their language near the place you got teleported.

Your task

Your job is to write an LL(1) parser, that can determine whether a specific string belongs to the specified grammar or not and also return the rules that were used during parsing. Your fingers are a bit strained because of the teleporting, so you want to code this parser in as less characters as possible.

Also it looks like for some weird reason there is free wifi there, but only wikipedia is available, so if you need help you can check how to parse an LL(1) grammar and how to create the parsing table for it.

Input

The first line of the input is the string you need to parse. The following lines will all include the available rules of the grammar, where the first character is the left hand side of the rule, and the rest of the line is the right hand side of the rule.

Example input:

(a+a)
SF
S(S+F)
Fa

Which describes that you have to determine whether ( a + a ) is part of the following grammar or not:

S → F
S → ( S + F )
F → a

Notes on the input:

• The grammar might contain empty (epsilon) rules, here the the right hand side is empty
• All terminals and non terminals occupy exactly one character
• Terminals are the following characters: abcdefghijlkmnopqrstuvwxyz+-/*^%=()[]{}
• Non Terminals are the following characters: ABCDEFGHIJKLMNOPQRSTUVWXYZ
• The starting non terminal is always S
• You can assume that the grammar in the input is always a proper LL(1) grammar
• A trailing newline may or may not be present, your choice.

Output

The output should contain whether the string is part of the grammar or not, and if it is, it should also include the rules you had to use for parsing.

Example output for the input above:

true
S(S+F)
SF
Fa
Fa

Variations on the output is allowed as long as it returns all information required. For example the following output is considered accepted as well: 1 [2,1,3,3] (1 because the string is accepted, then [2,1,3,3] are the rules used as an array, where each element represents the index of the rule in the input starting from one)

Scoring

You have to write either a complete program (reading from STDIN) or a function (reading from a string). The output can either be done to STDOUT, or returned from the function in an appropriate way (like a Pair<bool,int[]>).

Your point score is the byte count of the program, with the following penalties:

• Add 10 to the byte count and square it, in case you are using a built in LL(1) parser of your chosen language
• Add 100 to the byte count and square it, in case you are using a built in LL(2+), LR(1), LALR, SLR, or any other more advanced parser than LL(1)
• Although they might not be more advanced than an LL(1), use the previous penalty if you are using regular expression features which are not considered part of a regular grammar

(these penalties apply, since the teleporter messed up these built in functions a bit, and you have to magically fix them first)

Note:

Normal regular expressions are allowed and don't count into the penalty, unless you use advanced regexp features which make your expression not a regular grammar anymore. Also using a built in LR(0) parser is okay (but probably not very helpful)

Lowest points win.

If your language is not character based use the appropriate metric for your language and then apply the penalties on the resulting number. Standard loopholes apply, but solutions where the language was updated since the post was posted are allowed given you add the proper disclaimer to your post.

Examples

In:

(a+a)
SF
S(S+F)
Fa

Out: 1 [2,1,3,3]

In:

(aa)
SF
S(S+F)
Fa

Out: 0

In:

a*(a+a)
STE
E+TE
E
TFU
U*FU
U
F(S)
Fa

Out: 1 [1,4,8,5,7,1,4,8,6,2,4,8,6,3,6,3]

In:

aaabbb
SaA
AaAb
Ab

Out: 1 [1,2,2,3]

In:

aabbb
SaA
AaAb
Ab

Out: 0

In:

aaabb
SaA
AaAb
Ab

Out: 0

Answer 1

JavaScript (ES6), 177 bytes

177 looks like LL1 rotated 177°, so I stopped golfing.

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]

Try it online!

Outputs false if the string does not match, otherwise outputs a nested array of rule indices and terminals:

[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
  }
}

Answer 2

Python3, 672 bytes

E=enumerate
def F(b,g):
 if not b[0].isupper():yield b[0]
 for a,*B in g:
  if b[0]==a:yield from F(B*(B!=[' '])+b[1:],g)
def T(a,g):
 q=[(a,b,[])for A,*b in g if A==a]
 for A,b,s in q:
  for i,j in enumerate(b):
   if j==a and b[i+1:]and not b[i+1].isupper():yield b[i+1]
   for J,*k in g:
    if j==J and j not in s:q+=[(J,b[:i]+k*(k!=[' '])+b[i+1:],s+[j])]
def f(g):
 l,*g=g
 D={i[0]:{}for i in g}
 for i,(a,*b)in E(g):
  K=[*F(b,g)]
  for j in K:D[a][j]=i
  if' 'in K:
   for j in{*T(a,g)}:D[a][j]=i
 q,R=['S'],[]
 l+=[' ']
 while q:
  a,b=q.pop(0),l.pop(0)
  if a!=b:
   if a not in D:return
   q=[t for t in g[D[a][b]][1:]if' '!=t]+q;l=[b]+l;R+=[D[a][b]+1]
 return R

Try it online!